<!DOCTYPE html>
<html lang="zh-CN">
    <!-- title -->




<!-- keywords -->




<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=no" >
    <meta name="author" content="XiaoQixian">
    <meta name="renderer" content="webkit">
    <meta name="copyright" content="XiaoQixian">
    
    <meta name="keywords" content="hexo,hexo-theme,hexo-blog">
    
    <meta name="description" content="A man can be destoryed but not defeated">
    <meta name="description" content="红黑树(R-B Tree) 本文属于半转载：是根据多篇介绍文章加上自己的理解写成。文章地址：   https:&#x2F;&#x2F;www.cnblogs.com&#x2F;skywang12345&#x2F;p&#x2F;3245399.html https:&#x2F;&#x2F;www.jianshu.com&#x2F;p&#x2F;e136ec79235c  红黑树的特性 每个节点或者是黑色，或者是红色 根节点是黑色 每个为空的叶子结点为黑色 如果一个节点是红色的，则子节点必">
<meta property="og:type" content="article">
<meta property="og:title" content="红黑树">
<meta property="og:url" content="http://xiaoqixian.github.io.com/2020/04/26/%E7%BA%A2%E9%BB%91%E6%A0%91/index.html">
<meta property="og:site_name" content="Lunar">
<meta property="og:description" content="红黑树(R-B Tree) 本文属于半转载：是根据多篇介绍文章加上自己的理解写成。文章地址：   https:&#x2F;&#x2F;www.cnblogs.com&#x2F;skywang12345&#x2F;p&#x2F;3245399.html https:&#x2F;&#x2F;www.jianshu.com&#x2F;p&#x2F;e136ec79235c  红黑树的特性 每个节点或者是黑色，或者是红色 根节点是黑色 每个为空的叶子结点为黑色 如果一个节点是红色的，则子节点必">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://images0.cnblogs.com/i/497634/201403/251733282013849.jpg">
<meta property="og:image" content="https://images0.cnblogs.com/i/497634/201403/251734577643655.jpg">
<meta property="og:image" content="https://images0.cnblogs.com/i/497634/201403/251735527958942.jpg">
<meta property="og:image" content="https://images0.cnblogs.com/i/497634/201403/251737465769614.jpg">
<meta property="og:image" content="https://images0.cnblogs.com/i/497634/201403/251801031546918.jpg">
<meta property="og:image" content="https://images0.cnblogs.com/i/497634/201404/170945094945387.jpg">
<meta property="og:image" content="https://upload-images.jianshu.io/upload_images/2392382-dc4f0ab5d111ff96.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/806/format/webp">
<meta property="og:image" content="https://upload-images.jianshu.io/upload_images/2392382-f45799daa674d0ad.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1200/format/webp">
<meta property="og:image" content="https://upload-images.jianshu.io/upload_images/2392382-edaf96e55f08c198.png?imageMogr2/auto-orient/strip%7CimageView2/2/format/webp">
<meta property="article:published_time" content="2020-04-25T16:00:00.000Z">
<meta property="article:modified_time" content="2020-04-27T06:54:50.509Z">
<meta property="article:author" content="XiaoQixian">
<meta property="article:tag" content="DataStructure">
<meta property="article:tag" content="BinaryTree">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://images0.cnblogs.com/i/497634/201403/251733282013849.jpg">
    <meta http-equiv="Cache-control" content="no-cache">
    <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1"/>
    
    <title>红黑树 · LunarRoom</title>
    <style type="text/css">
    @font-face {
        font-family: 'Oswald-Regular';
        src: url("/font/Oswald-Regular.ttf");
    }

    body {
        margin: 0;
    }

    header,
    footer,
    .back-top,
    .sidebar,
    .container,
    .site-intro-meta,
    .toc-wrapper {
        display: none;
    }

    .site-intro {
        position: relative;
        z-index: 3;
        width: 100%;
        /* height: 50vh; */
        overflow: hidden;
    }

    .site-intro-placeholder {
        position: absolute;
        z-index: -2;
        top: 0;
        left: 0;
        width: calc(100% + 300px);
        height: 100%;
        background: repeating-linear-gradient(-45deg, #444 0, #444 80px, #333 80px, #333 160px);
        background-position: center center;
        transform: translate3d(-226px, 0, 0);
        animation: gradient-move 2.5s ease-out 0s infinite;
    }

    @keyframes gradient-move {
        0% {
            transform: translate3d(-226px, 0, 0);
        }
        100% {
            transform: translate3d(0, 0, 0);
        }
    }

</style>

    <link rel="preload" href= "/css/style.css?v=20180824" as="style" onload="this.onload=null;this.rel='stylesheet'" />
    <link rel="stylesheet" href= "/css/mobile.css?v=20180824" media="(max-width: 980px)">
    
    <link rel="preload" href="https://cdnjs.cloudflare.com/ajax/libs/fancybox/3.2.5/jquery.fancybox.min.css" as="style" onload="this.onload=null;this.rel='stylesheet'" />
    
    <!-- /*! loadCSS. [c]2017 Filament Group, Inc. MIT License */
/* This file is meant as a standalone workflow for
- testing support for link[rel=preload]
- enabling async CSS loading in browsers that do not support rel=preload
- applying rel preload css once loaded, whether supported or not.
*/ -->
<script>
(function( w ){
	"use strict";
	// rel=preload support test
	if( !w.loadCSS ){
		w.loadCSS = function(){};
	}
	// define on the loadCSS obj
	var rp = loadCSS.relpreload = {};
	// rel=preload feature support test
	// runs once and returns a function for compat purposes
	rp.support = (function(){
		var ret;
		try {
			ret = w.document.createElement( "link" ).relList.supports( "preload" );
		} catch (e) {
			ret = false;
		}
		return function(){
			return ret;
		};
	})();

	// if preload isn't supported, get an asynchronous load by using a non-matching media attribute
	// then change that media back to its intended value on load
	rp.bindMediaToggle = function( link ){
		// remember existing media attr for ultimate state, or default to 'all'
		var finalMedia = link.media || "all";

		function enableStylesheet(){
			link.media = finalMedia;
		}

		// bind load handlers to enable media
		if( link.addEventListener ){
			link.addEventListener( "load", enableStylesheet );
		} else if( link.attachEvent ){
			link.attachEvent( "onload", enableStylesheet );
		}

		// Set rel and non-applicable media type to start an async request
		// note: timeout allows this to happen async to let rendering continue in IE
		setTimeout(function(){
			link.rel = "stylesheet";
			link.media = "only x";
		});
		// also enable media after 3 seconds,
		// which will catch very old browsers (android 2.x, old firefox) that don't support onload on link
		setTimeout( enableStylesheet, 3000 );
	};

	// loop through link elements in DOM
	rp.poly = function(){
		// double check this to prevent external calls from running
		if( rp.support() ){
			return;
		}
		var links = w.document.getElementsByTagName( "link" );
		for( var i = 0; i < links.length; i++ ){
			var link = links[ i ];
			// qualify links to those with rel=preload and as=style attrs
			if( link.rel === "preload" && link.getAttribute( "as" ) === "style" && !link.getAttribute( "data-loadcss" ) ){
				// prevent rerunning on link
				link.setAttribute( "data-loadcss", true );
				// bind listeners to toggle media back
				rp.bindMediaToggle( link );
			}
		}
	};

	// if unsupported, run the polyfill
	if( !rp.support() ){
		// run once at least
		rp.poly();

		// rerun poly on an interval until onload
		var run = w.setInterval( rp.poly, 500 );
		if( w.addEventListener ){
			w.addEventListener( "load", function(){
				rp.poly();
				w.clearInterval( run );
			} );
		} else if( w.attachEvent ){
			w.attachEvent( "onload", function(){
				rp.poly();
				w.clearInterval( run );
			} );
		}
	}


	// commonjs
	if( typeof exports !== "undefined" ){
		exports.loadCSS = loadCSS;
	}
	else {
		w.loadCSS = loadCSS;
	}
}( typeof global !== "undefined" ? global : this ) );
</script>

    <link rel="icon" href= "/assets/bird.ico" />
    <link rel="preload" href="https://cdn.jsdelivr.net/npm/webfontloader@1.6.28/webfontloader.min.js" as="script" />
    <link rel="preload" href="https://cdn.jsdelivr.net/npm/jquery@3.3.1/dist/jquery.min.js" as="script" />
    <link rel="preload" href="/scripts/main.js" as="script" />
    <link rel="preload" as="font" href="/font/Oswald-Regular.ttf" crossorigin>
    <link rel="preload" as="font" href="https://at.alicdn.com/t/font_327081_1dta1rlogw17zaor.woff" crossorigin>
    
    <!-- fancybox -->
    <script src="https://cdnjs.cloudflare.com/ajax/libs/fancybox/3.2.5/jquery.fancybox.min.js" defer></script>
    <!-- 百度统计  -->
    
    <!-- 谷歌统计  -->
    
<meta name="generator" content="Hexo 4.2.0"></head>

    
        <body class="post-body">
    
    
<header class="header">

    <div class="read-progress"></div>
    <div class="header-sidebar-menu">&#xe775;</div>
    <!-- post页的toggle banner  -->
    
    <div class="banner">
            <div class="blog-title">
                <a href="/" >LunarRoom</a>
            </div>
            <div class="post-title">
                <a href="#" class="post-name">红黑树</a>
            </div>
    </div>
    
    <a class="home-link" href=/>LunarRoom</a>
</header>
    <div class="wrapper">
        <div class="site-intro" style="







height:50vh;
">
    
    <!-- 主页  -->
    
    
    <!-- 404页  -->
            
    <div class="site-intro-placeholder"></div>
    <div class="site-intro-img" style="background-image: url(/intro/fengling.jpg)"></div>
    <div class="site-intro-meta">
        <!-- 标题  -->
        <h1 class="intro-title">
            <!-- 主页  -->
            
            红黑树
            <!-- 404 -->
            
        </h1>
        <!-- 副标题 -->
        <p class="intro-subtitle">
            <!-- 主页副标题  -->
            
            
            <!-- 404 -->
            
        </p>
        <!-- 文章页meta -->
        
            <div class="post-intros">
                <!-- 文章页标签  -->
                
                    <div class= post-intro-tags >
    
        <a class="post-tag" href="javascript:void(0);" data-tags = "DataStructure">DataStructure</a>
    
        <a class="post-tag" href="javascript:void(0);" data-tags = "BinaryTree">BinaryTree</a>
    
</div>
                
                
                    <div class="post-intro-read">
                        <span>字数统计: <span class="post-count word-count">7.2k</span>阅读时长: <span class="post-count reading-time">32 min</span></span>
                    </div>
                
                <div class="post-intro-meta">
                    <span class="post-intro-calander iconfont-archer">&#xe676;</span>
                    <span class="post-intro-time">2020/04/26</span>
                    
                    <span id="busuanzi_container_page_pv" class="busuanzi-pv">
                        <span class="iconfont-archer">&#xe602;</span>
                        <span id="busuanzi_value_page_pv"></span>
                    </span>
                    
                    <span class="shareWrapper">
                        <span class="iconfont-archer shareIcon">&#xe71d;</span>
                        <span class="shareText">Share</span>
                        <ul class="shareList">
                            <li class="iconfont-archer share-qr" data-type="qr">&#xe75b;
                                <div class="share-qrcode"></div>
                            </li>
                            <li class="iconfont-archer" data-type="weibo">&#xe619;</li>
                            <li class="iconfont-archer" data-type="qzone">&#xe62e;</li>
                            <li class="iconfont-archer" data-type="twitter">&#xe634;</li>
                            <li class="iconfont-archer" data-type="facebook">&#xe67a;</li>
                        </ul>
                    </span>
                </div>
            </div>
        
    </div>
</div>
        <script>
 
  // get user agent
  var browser = {
    versions: function () {
      var u = window.navigator.userAgent;
      return {
        userAgent: u,
        trident: u.indexOf('Trident') > -1, //IE内核
        presto: u.indexOf('Presto') > -1, //opera内核
        webKit: u.indexOf('AppleWebKit') > -1, //苹果、谷歌内核
        gecko: u.indexOf('Gecko') > -1 && u.indexOf('KHTML') == -1, //火狐内核
        mobile: !!u.match(/AppleWebKit.*Mobile.*/), //是否为移动终端
        ios: !!u.match(/\(i[^;]+;( U;)? CPU.+Mac OS X/), //ios终端
        android: u.indexOf('Android') > -1 || u.indexOf('Linux') > -1, //android终端或者uc浏览器
        iPhone: u.indexOf('iPhone') > -1 || u.indexOf('Mac') > -1, //是否为iPhone或者安卓QQ浏览器
        iPad: u.indexOf('iPad') > -1, //是否为iPad
        webApp: u.indexOf('Safari') == -1, //是否为web应用程序，没有头部与底部
        weixin: u.indexOf('MicroMessenger') == -1, //是否为微信浏览器
        uc: u.indexOf('UCBrowser') > -1 //是否为android下的UC浏览器
      };
    }()
  }
  console.log("userAgent:" + browser.versions.userAgent);

  // callback
  function fontLoaded() {
    console.log('font loaded');
    if (document.getElementsByClassName('site-intro-meta')) {
      document.getElementsByClassName('intro-title')[0].classList.add('intro-fade-in');
      document.getElementsByClassName('intro-subtitle')[0].classList.add('intro-fade-in');
      var postIntros = document.getElementsByClassName('post-intros')[0]
      if (postIntros) {
        postIntros.classList.add('post-fade-in');
      }
    }
  }

  // UC不支持跨域，所以直接显示
  function asyncCb(){
    if (browser.versions.uc) {
      console.log("UCBrowser");
      fontLoaded();
    } else {
      WebFont.load({
        custom: {
          families: ['Oswald-Regular']
        },
        loading: function () {  //所有字体开始加载
          // console.log('loading');
        },
        active: function () {  //所有字体已渲染
          fontLoaded();
        },
        inactive: function () { //字体预加载失败，无效字体或浏览器不支持加载
          console.log('inactive: timeout');
          fontLoaded();
        },
        timeout: 5000 // Set the timeout to two seconds
      });
    }
  }

  function asyncErr(){
    console.warn('script load from CDN failed, will load local script')
  }

  // load webfont-loader async, and add callback function
  function async(u, cb, err) {
    var d = document, t = 'script',
      o = d.createElement(t),
      s = d.getElementsByTagName(t)[0];
    o.src = u;
    if (cb) { o.addEventListener('load', function (e) { cb(null, e); }, false); }
    if (err) { o.addEventListener('error', function (e) { err(null, e); }, false); }
    s.parentNode.insertBefore(o, s);
  }

  var asyncLoadWithFallBack = function(arr, success, reject) {
      var currReject = function(){
        reject()
        arr.shift()
        if(arr.length)
          async(arr[0], success, currReject)
        }

      async(arr[0], success, currReject)
  }

  asyncLoadWithFallBack([
    "https://cdn.jsdelivr.net/npm/webfontloader@1.6.28/webfontloader.min.js", 
    "https://cdn.bootcss.com/webfont/1.6.28/webfontloader.js",
    "/lib/webfontloader.min.js"
  ], asyncCb, asyncErr)
</script>        
        <img class="loading" src="/assets/loading.svg" style="display: block; margin: 6rem auto 0 auto; width: 6rem; height: 6rem;" />
        <div class="container container-unloaded">
            <main class="main post-page">
    <article class="article-entry">
        <h3 id="红黑树-R-B-Tree"><a href="#红黑树-R-B-Tree" class="headerlink" title="红黑树(R-B Tree)"></a><strong>红黑树(R-B Tree)</strong></h3><blockquote>
<p>本文属于半转载：是根据多篇介绍文章加上自己的理解写成。文章地址：   <a href="https://www.cnblogs.com/skywang12345/p/3245399.html" target="_blank" rel="noopener">https://www.cnblogs.com/skywang12345/p/3245399.html</a></p>
<p><a href="https://www.jianshu.com/p/e136ec79235c" target="_blank" rel="noopener">https://www.jianshu.com/p/e136ec79235c</a></p>
</blockquote>
<h4 id="红黑树的特性"><a href="#红黑树的特性" class="headerlink" title="红黑树的特性"></a><strong>红黑树的特性</strong></h4><ol>
<li>每个节点或者是黑色，或者是红色</li>
<li>根节点是黑色</li>
<li>每个为空的叶子结点为黑色</li>
<li>如果一个节点是红色的，则子节点必须是黑色的</li>
<li>从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。这一点可以确保红黑树不会一条路径过长，保证是一个相对平衡的树</li>
</ol>
<h4 id="红黑树的应用"><a href="#红黑树的应用" class="headerlink" title="红黑树的应用"></a><strong>红黑树的应用</strong></h4><p>红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(lgn)，效率非常之高。<br>例如，Java集合中的<a href="http://www.cnblogs.com/skywang12345/p/3311268.html" target="_blank" rel="noopener">TreeSet</a>和<a href="http://www.cnblogs.com/skywang12345/p/3310928.html" target="_blank" rel="noopener">TreeMap</a>，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。</p>
<p>而红黑树快的根本就在于它通过一系列的规则使得这棵二叉查找树编程一棵自平衡的二叉查找树，不会出现某一个分支过长的情况。</p>
<h4 id="左旋与右旋"><a href="#左旋与右旋" class="headerlink" title="左旋与右旋"></a><strong>左旋与右旋</strong></h4><p>红黑树需要经常进行添加或删除的操作，但是由于红黑树的要求非常高，在经过添加或删除的操作后就不是红黑树了，需要通过旋转来保持红黑树的特性。</p>
<ol>
<li><p><strong>左旋</strong></p>
<p><img src="https://images0.cnblogs.com/i/497634/201403/251733282013849.jpg" alt=""></p>
<p>操作步骤：</p>
<ul>
<li>将Y的左节点$\beta$设为X的右节点并将$\beta$节点的父节点更改为X</li>
<li>将Y的父节点设为X的父节点，进行判断，如果X的父节点是空节点，则将Y节点设为root节点。如果不为空，则将对应父节点的子节点设为Y</li>
<li>将X设为Y的左节点</li>
<li>将X的父节点设为Y</li>
</ul>
<p>事实上不一定要按照这种步骤，要实现图中的效果，可以由多种实现方法。</p>
<p><img src="https://images0.cnblogs.com/i/497634/201403/251734577643655.jpg" alt=""></p>
</li>
<li><p><strong>右旋</strong></p>
<p><img src="https://images0.cnblogs.com/i/497634/201403/251735527958942.jpg" alt=""></p>
<p>与左旋类似，略</p>
<p><img src="https://images0.cnblogs.com/i/497634/201403/251737465769614.jpg" alt=""></p>
</li>
</ol>
<p>总结来说：左旋的操作可以使得当前节点与左子节点交换位置，使得自己成为左子节点；右旋的操作可以使得当前节点（父节点的右节点）与父节点交换位置，使得自己成为父节点并使父节点成为自己的左节点。</p>
<h4 id="添加节点"><a href="#添加节点" class="headerlink" title="添加节点"></a><strong>添加节点</strong></h4><p>核心思想：<strong>将红色节点移到根节点，将根节点涂黑</strong></p>
<p>为了使添加节点后违背的红黑树的特性条数最少，我们考虑将新添加的节点颜色设为红色，这样只会有可能违背特性4。</p>
<p>然后开始插入新节点，由于<strong>红黑树首先是一棵二叉查找树</strong>，所以先根据要插入的节点的值的大小找到要插入的位置。</p>
<p>插入节点后有三种情况：</p>
<ul>
<li>插入后父节点是根节点，则将插入节点涂成黑色。</li>
<li>插入后父节点不是根节点，但是是黑色节点，不需要任何操作此树依旧是一棵红黑树。</li>
<li>插入后父节点是红色节点。需要再进行分情况。</li>
</ul>
<p><strong>插入后父节点是红色节点</strong></p>
<ul>
<li><p><strong>叔叔节点是红色</strong></p>
<p>处理策略：</p>
<ul>
<li>将父节点设为黑色</li>
<li>叔叔节点设为黑色</li>
<li>祖父节点设为红色</li>
<li>将祖父节点作为当前节点进行递归</li>
</ul>
<p>首先，若父节点是红色的，则直接违背了特性3。于是将父节点涂成黑色的，这样就违背了特性5。因为在插入新节点之前，该树已经是一棵红黑树，说明父节点及以上的节点到负节点和到叔叔节点的黑色节点是一样的，现在父节点变黑了，到父节点的路径就多了一个黑节点，需要将叔叔节点也涂黑。</p>
<p>但是这样变换会带来新的问题，虽然到父节点和到叔叔节点的路径黑节点数量平衡了，但是对于祖父节点及以上的节点来说，走祖父节点的这条路径的黑色节点多了一个，所以需要将祖父节点涂红平衡。为什么祖父节点一定是黑色呢？因为父节点和叔叔节点都是红色的，祖父不可能是红色的。</p>
<p>但是这样对于祖父节点以上的节点又不平衡了，所以需要将祖父节点作为当前节点继续进行等效的插入操作。直到递归到根节点，而前面提到，如果祖父节点就是根节点的话，直接将祖父节点涂黑便可。</p>
</li>
<li><p><strong>叔叔节点是黑色，且当前节点是右节点</strong></p>
<p>处理策略：</p>
<ul>
<li>将父节点作为新的当前节点</li>
<li>以新的当前节点作为支点进行左旋</li>
</ul>
<p>這樣的處理策略可以使得紅黑樹變成情景3的結構，所以轉到情景3.</p>
<p>示意图：</p>
<p><img src="https://images0.cnblogs.com/i/497634/201403/251801031546918.jpg" alt=""></p>
</li>
<li><p>叔叔节点是黑色，且当前节点是左节点</p>
<p>处理策略：</p>
<ul>
<li>将父节点设为黑色</li>
<li>将祖父节点设为红色</li>
<li>以祖父节点为支点进行右旋</li>
</ul>
<p>經過這樣的處理後就變成了情景1的狀況。再將祖父節點作為當前節點後就可以逐漸將紅色節點移動到根節點，再直接塗黑。這就體現了紅黑樹添加節點的核心思想：<strong>將紅色節點通過塗顏色和旋轉的方式移動到根節點後直接塗黑</strong>。</p>
<p>示意图：</p>
<p><img src="https://images0.cnblogs.com/i/497634/201404/170945094945387.jpg" alt=""></p>
</li>
</ul>
<h4 id="删除节点"><a href="#删除节点" class="headerlink" title="删除节点"></a><strong>删除节点</strong></h4><p>删除节点是红黑树操作最难的部分。</p>
<p>首先通过查找操作找到要删除的节点，这个不难操作。</p>
<p>先不考虑红黑树的平衡问题，只先考慮如何删除一个节点。</p>
<ul>
<li><p>情景1：如果要删除的节点没有子节点，则直接删除</p>
</li>
<li><p>情景2：如果要删除的节点只有一个子节点，则用子节点替换删除的节点</p>
</li>
<li><p>情景3：若删除节点有两个子节点，用后继节点（大于删除节点的最小节点）替换删除节点</p>
<p>大于删除节点的最小节点即删除节点的右子树的最左节点</p>
<p>把二叉树的所有节点投射在X轴上，所有节点都是从左到右排好序的，所有目标节点的前后节点就是对应前继和后继节点。</p>
<p><img src="https://upload-images.jianshu.io/upload_images/2392382-dc4f0ab5d111ff96.png?imageMogr2/auto-orient/strip|imageView2/2/w/806/format/webp" alt=""></p>
</li>
</ul>
<p>一个删除节点的重要思想：<strong>删除节点被替代后，对于树来说，可以认为删除的是替代节点</strong>。</p>
<p><img src="https://upload-images.jianshu.io/upload_images/2392382-f45799daa674d0ad.png?imageMogr2/auto-orient/strip|imageView2/2/w/1200/format/webp" alt=""></p>
<p>根据这个思想，可以将三种情景都转换为情景1。</p>
<ul>
<li>情景2：删除结点用其唯一的子结点替换，子结点替换为删除结点后，可以认为删除的是子结点，若子结点又有两个子结点，那么相当于转换为情景3，一直自顶向下转换，总是能转换为情景1。（对于红黑树来说，只存在一个子结点的结点肯定在树末了）</li>
<li>情景3：删除结点用后继结点（肯定不存在左结点，因为后继节点为大于删除节点的最左节点），如果后继结点有右子结点，那么相当于转换为情景2，否则转为为情景1。</li>
</ul>
<p>总结：<strong>删除操作删除的结点可以看作删除替代结点，而替代结点最后总是在树末</strong>。這裡說的刪除替代節點並不是真的將替代節點刪除，而是將需要被刪除的節點刪除，將替代節點移動到被刪除節點的位置，二叉查找樹（不考慮顏色）依舊保持穩定。</p>
<p>接下來就只需考慮刪除節點後的紅黑樹的自平衡問題。</p>
<p><strong>红黑树删除场景</strong></p>
<p>提示：裡面列出的許多場景在正常的紅黑樹可能不會遇到，但是在其他場景中經過變換後可能得到那些場景，所以加上了處理情況。</p>
<p><img src="https://upload-images.jianshu.io/upload_images/2392382-edaf96e55f08c198.png?imageMogr2/auto-orient/strip|imageView2/2/format/webp" alt=""></p>
<ul>
<li><p>場景1：替換節點是紅色節點</p>
<p>由於替換節點是紅色，即使刪除了也不會影響紅黑樹的平衡，所以直接將替換節點的顏色設為刪除節點的顏色就可以保持紅黑樹的平衡。</p>
</li>
<li><p>場景2：替換節點是黑節點</p>
<p>需要根據不同的場景進行不同的旋轉操作</p>
<ul>
<li><p>場景2.1：替換節點是其父節點的左子節點</p>
<ul>
<li><p>場景2.1.1：替換節點的兄弟節點是紅節點</p>
<p><strong>處理</strong>：</p>
<p>將兄弟節點設為黑色，父節點設為紅色，對父節點進行左旋。</p>
</li>
<li><p>場景2.1.2：替換節點的兄弟節點是黑節點</p>
<ul>
<li><p>場景2.1.2.1：替換節點的兄弟節點的右子節點是紅節點，左子節點為任意顏色。</p>
<p>處理：</p>
<ul>
<li>將兄弟節點的顏色設為父節點的顏色</li>
<li>將父節點涂為黑色</li>
<li>將兄弟節點的右節點設為黑色</li>
<li>對父節點進行左旋</li>
</ul>
</li>
<li><p>場景2.1.2.2：替換節點的兄弟節點的右子節點為黑節點，左子節點為紅節點。</p>
<p>處理：</p>
<ul>
<li>將兄弟節點設為紅節點</li>
<li>兄弟節點左節點設為黑節點</li>
<li>對兄弟節點右旋，可得到2.1.2.1的場景，繼續進行處理</li>
</ul>
</li>
<li><p>場景2.1.2.3：替換節點的兄弟節點的子節點都為黑節點</p>
<p>處理：</p>
<ul>
<li>將兄弟節點設為紅色</li>
<li>將父節點作為新的替換節點進行考慮</li>
</ul>
<p>等於是讓父節點的兩棵子樹強行平衡，然後自己作為新的替換節點到上層去“想辦法”。</p>
</li>
</ul>
</li>
</ul>
</li>
<li><p>場景2.2：替換節點是父節點的右節點</p>
<ul>
<li><p>場景2.2.1：兄弟節點是紅節點</p>
<p>處理：</p>
<ul>
<li>兄弟節點設為父節點的顏色</li>
<li>父節點設為紅色</li>
<li>對父節點進行右旋，得到場景2.2.2.3</li>
<li>進行場景2.2.2.3的處理</li>
</ul>
</li>
<li><p>場景2.2.2：兄弟節點是黑節點</p>
<ul>
<li><p>場景2.2.2.1：兄弟節點的左自子節點是紅節點，右子節點任意顏色</p>
<p>處理：</p>
<ul>
<li>兄弟節點設為父節點的顏色</li>
<li>父節點設為黑色</li>
<li>兄弟節點的左子節點設為黑色</li>
<li>對父節點進行右旋</li>
</ul>
</li>
<li><p>場景2.2.2.2：兄弟節點的左子節點為黑節點，右子節點為紅節點</p>
<p>處理：</p>
<ul>
<li>兄弟節點設為紅色</li>
<li>兄弟節點的右子節點設為黑色</li>
<li>對兄弟節點進行左旋，得到場景2.2.2.1</li>
<li>進行場景2.2.2.1的處理</li>
</ul>
</li>
<li><p>場景2.2.2.3：替換節點的兄弟節點的子節點均為黑節點</p>
<p>處理：</p>
<ul>
<li>兄弟節點設為黑色</li>
<li>將父節點作為新的替換節點重新進行場景處理</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
<hr>
<h4 id="Visualization"><a href="#Visualization" class="headerlink" title="Visualization"></a><strong>Visualization</strong></h4><p>我認為學習數據結構，可視化是一個很大的幫助。前幾天找到一篇大神寫的紅黑樹可視化的前端代碼，分享給大家。大神博客在源碼中有</p>
<figure class="highlight html"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br><span class="line">171</span><br><span class="line">172</span><br><span class="line">173</span><br><span class="line">174</span><br><span class="line">175</span><br><span class="line">176</span><br><span class="line">177</span><br><span class="line">178</span><br><span class="line">179</span><br><span class="line">180</span><br><span class="line">181</span><br><span class="line">182</span><br><span class="line">183</span><br><span class="line">184</span><br><span class="line">185</span><br><span class="line">186</span><br><span class="line">187</span><br><span class="line">188</span><br><span class="line">189</span><br><span class="line">190</span><br><span class="line">191</span><br><span class="line">192</span><br><span class="line">193</span><br><span class="line">194</span><br><span class="line">195</span><br><span class="line">196</span><br><span class="line">197</span><br><span class="line">198</span><br><span class="line">199</span><br><span class="line">200</span><br><span class="line">201</span><br><span class="line">202</span><br><span class="line">203</span><br><span class="line">204</span><br><span class="line">205</span><br><span class="line">206</span><br><span class="line">207</span><br><span class="line">208</span><br><span class="line">209</span><br><span class="line">210</span><br><span class="line">211</span><br><span class="line">212</span><br><span class="line">213</span><br><span class="line">214</span><br><span class="line">215</span><br><span class="line">216</span><br><span class="line">217</span><br><span class="line">218</span><br><span class="line">219</span><br><span class="line">220</span><br><span class="line">221</span><br><span class="line">222</span><br><span class="line">223</span><br><span class="line">224</span><br><span class="line">225</span><br><span class="line">226</span><br><span class="line">227</span><br><span class="line">228</span><br><span class="line">229</span><br><span class="line">230</span><br><span class="line">231</span><br><span class="line">232</span><br><span class="line">233</span><br><span class="line">234</span><br><span class="line">235</span><br><span class="line">236</span><br><span class="line">237</span><br><span class="line">238</span><br><span class="line">239</span><br><span class="line">240</span><br><span class="line">241</span><br><span class="line">242</span><br><span class="line">243</span><br><span class="line">244</span><br><span class="line">245</span><br><span class="line">246</span><br><span class="line">247</span><br><span class="line">248</span><br><span class="line">249</span><br><span class="line">250</span><br><span class="line">251</span><br><span class="line">252</span><br><span class="line">253</span><br><span class="line">254</span><br><span class="line">255</span><br><span class="line">256</span><br><span class="line">257</span><br><span class="line">258</span><br><span class="line">259</span><br><span class="line">260</span><br><span class="line">261</span><br><span class="line">262</span><br><span class="line">263</span><br><span class="line">264</span><br><span class="line">265</span><br><span class="line">266</span><br><span class="line">267</span><br><span class="line">268</span><br><span class="line">269</span><br><span class="line">270</span><br><span class="line">271</span><br><span class="line">272</span><br><span class="line">273</span><br><span class="line">274</span><br><span class="line">275</span><br><span class="line">276</span><br><span class="line">277</span><br><span class="line">278</span><br><span class="line">279</span><br><span class="line">280</span><br><span class="line">281</span><br><span class="line">282</span><br><span class="line">283</span><br><span class="line">284</span><br><span class="line">285</span><br><span class="line">286</span><br><span class="line">287</span><br><span class="line">288</span><br><span class="line">289</span><br><span class="line">290</span><br><span class="line">291</span><br><span class="line">292</span><br><span class="line">293</span><br><span class="line">294</span><br><span class="line">295</span><br><span class="line">296</span><br><span class="line">297</span><br><span class="line">298</span><br><span class="line">299</span><br><span class="line">300</span><br><span class="line">301</span><br><span class="line">302</span><br><span class="line">303</span><br><span class="line">304</span><br><span class="line">305</span><br><span class="line">306</span><br><span class="line">307</span><br><span class="line">308</span><br><span class="line">309</span><br><span class="line">310</span><br><span class="line">311</span><br><span class="line">312</span><br><span class="line">313</span><br><span class="line">314</span><br><span class="line">315</span><br><span class="line">316</span><br><span class="line">317</span><br><span class="line">318</span><br><span class="line">319</span><br><span class="line">320</span><br><span class="line">321</span><br><span class="line">322</span><br><span class="line">323</span><br><span class="line">324</span><br><span class="line">325</span><br><span class="line">326</span><br><span class="line">327</span><br><span class="line">328</span><br><span class="line">329</span><br><span class="line">330</span><br><span class="line">331</span><br><span class="line">332</span><br><span class="line">333</span><br><span class="line">334</span><br><span class="line">335</span><br><span class="line">336</span><br><span class="line">337</span><br><span class="line">338</span><br><span class="line">339</span><br><span class="line">340</span><br><span class="line">341</span><br><span class="line">342</span><br><span class="line">343</span><br><span class="line">344</span><br><span class="line">345</span><br><span class="line">346</span><br><span class="line">347</span><br><span class="line">348</span><br><span class="line">349</span><br><span class="line">350</span><br><span class="line">351</span><br><span class="line">352</span><br><span class="line">353</span><br><span class="line">354</span><br><span class="line">355</span><br><span class="line">356</span><br><span class="line">357</span><br><span class="line">358</span><br><span class="line">359</span><br><span class="line">360</span><br><span class="line">361</span><br><span class="line">362</span><br><span class="line">363</span><br><span class="line">364</span><br><span class="line">365</span><br><span class="line">366</span><br><span class="line">367</span><br><span class="line">368</span><br><span class="line">369</span><br><span class="line">370</span><br><span class="line">371</span><br><span class="line">372</span><br><span class="line">373</span><br><span class="line">374</span><br><span class="line">375</span><br><span class="line">376</span><br><span class="line">377</span><br><span class="line">378</span><br><span class="line">379</span><br><span class="line">380</span><br><span class="line">381</span><br><span class="line">382</span><br><span class="line">383</span><br><span class="line">384</span><br><span class="line">385</span><br><span class="line">386</span><br><span class="line">387</span><br><span class="line">388</span><br><span class="line">389</span><br><span class="line">390</span><br><span class="line">391</span><br><span class="line">392</span><br><span class="line">393</span><br><span class="line">394</span><br><span class="line">395</span><br><span class="line">396</span><br><span class="line">397</span><br><span class="line">398</span><br><span class="line">399</span><br><span class="line">400</span><br><span class="line">401</span><br><span class="line">402</span><br><span class="line">403</span><br><span class="line">404</span><br><span class="line">405</span><br><span class="line">406</span><br><span class="line">407</span><br><span class="line">408</span><br><span class="line">409</span><br><span class="line">410</span><br><span class="line">411</span><br><span class="line">412</span><br><span class="line">413</span><br><span class="line">414</span><br><span class="line">415</span><br><span class="line">416</span><br><span class="line">417</span><br><span class="line">418</span><br><span class="line">419</span><br><span class="line">420</span><br><span class="line">421</span><br><span class="line">422</span><br><span class="line">423</span><br><span class="line">424</span><br><span class="line">425</span><br><span class="line">426</span><br><span class="line">427</span><br><span class="line">428</span><br><span class="line">429</span><br><span class="line">430</span><br><span class="line">431</span><br><span class="line">432</span><br><span class="line">433</span><br><span class="line">434</span><br><span class="line">435</span><br><span class="line">436</span><br><span class="line">437</span><br><span class="line">438</span><br><span class="line">439</span><br><span class="line">440</span><br><span class="line">441</span><br><span class="line">442</span><br><span class="line">443</span><br><span class="line">444</span><br><span class="line">445</span><br><span class="line">446</span><br><span class="line">447</span><br><span class="line">448</span><br><span class="line">449</span><br><span class="line">450</span><br><span class="line">451</span><br><span class="line">452</span><br><span class="line">453</span><br><span class="line">454</span><br><span class="line">455</span><br><span class="line">456</span><br><span class="line">457</span><br><span class="line">458</span><br><span class="line">459</span><br><span class="line">460</span><br><span class="line">461</span><br><span class="line">462</span><br><span class="line">463</span><br><span class="line">464</span><br><span class="line">465</span><br><span class="line">466</span><br><span class="line">467</span><br><span class="line">468</span><br><span class="line">469</span><br><span class="line">470</span><br><span class="line">471</span><br><span class="line">472</span><br><span class="line">473</span><br><span class="line">474</span><br><span class="line">475</span><br><span class="line">476</span><br><span class="line">477</span><br><span class="line">478</span><br><span class="line">479</span><br><span class="line">480</span><br><span class="line">481</span><br><span class="line">482</span><br><span class="line">483</span><br><span class="line">484</span><br><span class="line">485</span><br><span class="line">486</span><br><span class="line">487</span><br><span class="line">488</span><br><span class="line">489</span><br><span class="line">490</span><br><span class="line">491</span><br><span class="line">492</span><br><span class="line">493</span><br><span class="line">494</span><br><span class="line">495</span><br><span class="line">496</span><br><span class="line">497</span><br><span class="line">498</span><br><span class="line">499</span><br><span class="line">500</span><br><span class="line">501</span><br><span class="line">502</span><br><span class="line">503</span><br><span class="line">504</span><br><span class="line">505</span><br><span class="line">506</span><br><span class="line">507</span><br><span class="line">508</span><br><span class="line">509</span><br><span class="line">510</span><br><span class="line">511</span><br><span class="line">512</span><br><span class="line">513</span><br><span class="line">514</span><br><span class="line">515</span><br><span class="line">516</span><br><span class="line">517</span><br><span class="line">518</span><br><span class="line">519</span><br><span class="line">520</span><br><span class="line">521</span><br><span class="line">522</span><br><span class="line">523</span><br><span class="line">524</span><br><span class="line">525</span><br><span class="line">526</span><br><span class="line">527</span><br><span class="line">528</span><br><span class="line">529</span><br><span class="line">530</span><br><span class="line">531</span><br><span class="line">532</span><br><span class="line">533</span><br><span class="line">534</span><br><span class="line">535</span><br><span class="line">536</span><br><span class="line">537</span><br><span class="line">538</span><br><span class="line">539</span><br><span class="line">540</span><br><span class="line">541</span><br><span class="line">542</span><br><span class="line">543</span><br><span class="line">544</span><br><span class="line">545</span><br><span class="line">546</span><br><span class="line">547</span><br><span class="line">548</span><br><span class="line">549</span><br><span class="line">550</span><br><span class="line">551</span><br><span class="line">552</span><br><span class="line">553</span><br><span class="line">554</span><br><span class="line">555</span><br><span class="line">556</span><br><span class="line">557</span><br><span class="line">558</span><br><span class="line">559</span><br><span class="line">560</span><br><span class="line">561</span><br><span class="line">562</span><br><span class="line">563</span><br><span class="line">564</span><br><span class="line">565</span><br><span class="line">566</span><br><span class="line">567</span><br><span class="line">568</span><br><span class="line">569</span><br><span class="line">570</span><br><span class="line">571</span><br><span class="line">572</span><br><span class="line">573</span><br><span class="line">574</span><br><span class="line">575</span><br><span class="line">576</span><br><span class="line">577</span><br><span class="line">578</span><br><span class="line">579</span><br><span class="line">580</span><br><span class="line">581</span><br><span class="line">582</span><br><span class="line">583</span><br><span class="line">584</span><br><span class="line">585</span><br><span class="line">586</span><br><span class="line">587</span><br><span class="line">588</span><br><span class="line">589</span><br><span class="line">590</span><br><span class="line">591</span><br><span class="line">592</span><br><span class="line">593</span><br><span class="line">594</span><br><span class="line">595</span><br><span class="line">596</span><br><span class="line">597</span><br><span class="line">598</span><br><span class="line">599</span><br><span class="line">600</span><br><span class="line">601</span><br><span class="line">602</span><br><span class="line">603</span><br><span class="line">604</span><br><span class="line">605</span><br><span class="line">606</span><br><span class="line">607</span><br><span class="line">608</span><br><span class="line">609</span><br><span class="line">610</span><br><span class="line">611</span><br><span class="line">612</span><br><span class="line">613</span><br><span class="line">614</span><br><span class="line">615</span><br><span class="line">616</span><br><span class="line">617</span><br><span class="line">618</span><br><span class="line">619</span><br><span class="line">620</span><br><span class="line">621</span><br><span class="line">622</span><br><span class="line">623</span><br><span class="line">624</span><br><span class="line">625</span><br><span class="line">626</span><br><span class="line">627</span><br><span class="line">628</span><br><span class="line">629</span><br><span class="line">630</span><br><span class="line">631</span><br><span class="line">632</span><br><span class="line">633</span><br><span class="line">634</span><br><span class="line">635</span><br><span class="line">636</span><br><span class="line">637</span><br><span class="line">638</span><br><span class="line">639</span><br><span class="line">640</span><br><span class="line">641</span><br><span class="line">642</span><br><span class="line">643</span><br><span class="line">644</span><br><span class="line">645</span><br><span class="line">646</span><br><span class="line">647</span><br><span class="line">648</span><br><span class="line">649</span><br><span class="line">650</span><br><span class="line">651</span><br><span class="line">652</span><br><span class="line">653</span><br><span class="line">654</span><br><span class="line">655</span><br><span class="line">656</span><br><span class="line">657</span><br><span class="line">658</span><br><span class="line">659</span><br><span class="line">660</span><br><span class="line">661</span><br><span class="line">662</span><br><span class="line">663</span><br><span class="line">664</span><br><span class="line">665</span><br><span class="line">666</span><br><span class="line">667</span><br><span class="line">668</span><br><span class="line">669</span><br><span class="line">670</span><br><span class="line">671</span><br><span class="line">672</span><br><span class="line">673</span><br><span class="line">674</span><br><span class="line">675</span><br><span class="line">676</span><br><span class="line">677</span><br><span class="line">678</span><br><span class="line">679</span><br><span class="line">680</span><br><span class="line">681</span><br><span class="line">682</span><br><span class="line">683</span><br><span class="line">684</span><br><span class="line">685</span><br><span class="line">686</span><br><span class="line">687</span><br><span class="line">688</span><br><span class="line">689</span><br><span class="line">690</span><br><span class="line">691</span><br><span class="line">692</span><br><span class="line">693</span><br><span class="line">694</span><br><span class="line">695</span><br><span class="line">696</span><br><span class="line">697</span><br><span class="line">698</span><br><span class="line">699</span><br><span class="line">700</span><br><span class="line">701</span><br><span class="line">702</span><br><span class="line">703</span><br><span class="line">704</span><br><span class="line">705</span><br><span class="line">706</span><br><span class="line">707</span><br><span class="line">708</span><br><span class="line">709</span><br><span class="line">710</span><br><span class="line">711</span><br><span class="line">712</span><br><span class="line">713</span><br><span class="line">714</span><br><span class="line">715</span><br><span class="line">716</span><br><span class="line">717</span><br><span class="line">718</span><br><span class="line">719</span><br><span class="line">720</span><br><span class="line">721</span><br><span class="line">722</span><br><span class="line">723</span><br><span class="line">724</span><br><span class="line">725</span><br><span class="line">726</span><br><span class="line">727</span><br><span class="line">728</span><br><span class="line">729</span><br><span class="line">730</span><br><span class="line">731</span><br><span class="line">732</span><br><span class="line">733</span><br><span class="line">734</span><br><span class="line">735</span><br><span class="line">736</span><br><span class="line">737</span><br><span class="line">738</span><br><span class="line">739</span><br><span class="line">740</span><br><span class="line">741</span><br><span class="line">742</span><br><span class="line">743</span><br><span class="line">744</span><br><span class="line">745</span><br><span class="line">746</span><br><span class="line">747</span><br><span class="line">748</span><br><span class="line">749</span><br><span class="line">750</span><br><span class="line">751</span><br><span class="line">752</span><br><span class="line">753</span><br><span class="line">754</span><br><span class="line">755</span><br><span class="line">756</span><br><span class="line">757</span><br><span class="line">758</span><br><span class="line">759</span><br><span class="line">760</span><br><span class="line">761</span><br><span class="line">762</span><br><span class="line">763</span><br><span class="line">764</span><br><span class="line">765</span><br><span class="line">766</span><br><span class="line">767</span><br><span class="line">768</span><br><span class="line">769</span><br><span class="line">770</span><br><span class="line">771</span><br><span class="line">772</span><br><span class="line">773</span><br><span class="line">774</span><br><span class="line">775</span><br><span class="line">776</span><br><span class="line">777</span><br><span class="line">778</span><br><span class="line">779</span><br><span class="line">780</span><br><span class="line">781</span><br><span class="line">782</span><br><span class="line">783</span><br><span class="line">784</span><br><span class="line">785</span><br><span class="line">786</span><br><span class="line">787</span><br><span class="line">788</span><br><span class="line">789</span><br><span class="line">790</span><br><span class="line">791</span><br><span class="line">792</span><br><span class="line">793</span><br><span class="line">794</span><br><span class="line">795</span><br><span class="line">796</span><br><span class="line">797</span><br><span class="line">798</span><br><span class="line">799</span><br><span class="line">800</span><br><span class="line">801</span><br><span class="line">802</span><br><span class="line">803</span><br><span class="line">804</span><br><span class="line">805</span><br><span class="line">806</span><br><span class="line">807</span><br><span class="line">808</span><br><span class="line">809</span><br><span class="line">810</span><br><span class="line">811</span><br><span class="line">812</span><br><span class="line">813</span><br><span class="line">814</span><br><span class="line">815</span><br><span class="line">816</span><br><span class="line">817</span><br><span class="line">818</span><br><span class="line">819</span><br><span class="line">820</span><br><span class="line">821</span><br><span class="line">822</span><br><span class="line">823</span><br><span class="line">824</span><br><span class="line">825</span><br><span class="line">826</span><br><span class="line">827</span><br><span class="line">828</span><br><span class="line">829</span><br><span class="line">830</span><br><span class="line">831</span><br><span class="line">832</span><br><span class="line">833</span><br><span class="line">834</span><br><span class="line">835</span><br><span class="line">836</span><br><span class="line">837</span><br><span class="line">838</span><br><span class="line">839</span><br><span class="line">840</span><br><span class="line">841</span><br><span class="line">842</span><br><span class="line">843</span><br><span class="line">844</span><br><span class="line">845</span><br><span class="line">846</span><br><span class="line">847</span><br><span class="line">848</span><br><span class="line">849</span><br><span class="line">850</span><br><span class="line">851</span><br><span class="line">852</span><br><span class="line">853</span><br><span class="line">854</span><br><span class="line">855</span><br><span class="line">856</span><br><span class="line">857</span><br><span class="line">858</span><br><span class="line">859</span><br><span class="line">860</span><br><span class="line">861</span><br><span class="line">862</span><br><span class="line">863</span><br><span class="line">864</span><br><span class="line">865</span><br><span class="line">866</span><br><span class="line">867</span><br><span class="line">868</span><br><span class="line">869</span><br><span class="line">870</span><br><span class="line">871</span><br><span class="line">872</span><br><span class="line">873</span><br><span class="line">874</span><br><span class="line">875</span><br><span class="line">876</span><br><span class="line">877</span><br><span class="line">878</span><br><span class="line">879</span><br><span class="line">880</span><br><span class="line">881</span><br><span class="line">882</span><br><span class="line">883</span><br><span class="line">884</span><br><span class="line">885</span><br><span class="line">886</span><br><span class="line">887</span><br><span class="line">888</span><br><span class="line">889</span><br><span class="line">890</span><br><span class="line">891</span><br><span class="line">892</span><br><span class="line">893</span><br><span class="line">894</span><br><span class="line">895</span><br><span class="line">896</span><br><span class="line">897</span><br><span class="line">898</span><br><span class="line">899</span><br><span class="line">900</span><br><span class="line">901</span><br><span class="line">902</span><br><span class="line">903</span><br><span class="line">904</span><br><span class="line">905</span><br><span class="line">906</span><br><span class="line">907</span><br><span class="line">908</span><br><span class="line">909</span><br><span class="line">910</span><br><span class="line">911</span><br><span class="line">912</span><br><span class="line">913</span><br><span class="line">914</span><br><span class="line">915</span><br><span class="line">916</span><br><span class="line">917</span><br><span class="line">918</span><br><span class="line">919</span><br><span class="line">920</span><br><span class="line">921</span><br><span class="line">922</span><br><span class="line">923</span><br><span class="line">924</span><br><span class="line">925</span><br><span class="line">926</span><br><span class="line">927</span><br><span class="line">928</span><br><span class="line">929</span><br><span class="line">930</span><br><span class="line">931</span><br><span class="line">932</span><br><span class="line">933</span><br><span class="line">934</span><br><span class="line">935</span><br><span class="line">936</span><br><span class="line">937</span><br><span class="line">938</span><br><span class="line">939</span><br><span class="line">940</span><br><span class="line">941</span><br><span class="line">942</span><br><span class="line">943</span><br><span class="line">944</span><br><span class="line">945</span><br><span class="line">946</span><br><span class="line">947</span><br><span class="line">948</span><br><span class="line">949</span><br><span class="line">950</span><br><span class="line">951</span><br><span class="line">952</span><br><span class="line">953</span><br><span class="line">954</span><br><span class="line">955</span><br><span class="line">956</span><br><span class="line">957</span><br><span class="line">958</span><br><span class="line">959</span><br><span class="line">960</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line"><span class="meta">&lt;!DOCTYPE <span class="meta-keyword">html</span>&gt;</span></span><br><span class="line"><span class="tag">&lt;<span class="name">html</span> <span class="attr">xmlns</span>=<span class="string">"http://www.w3.org/1999/xhtml"</span>&gt;</span></span><br><span class="line"><span class="tag">&lt;<span class="name">head</span>&gt;</span></span><br><span class="line">    <span class="tag">&lt;<span class="name">meta</span> <span class="attr">http-equiv</span>=<span class="string">"Content-Type"</span> <span class="attr">content</span>=<span class="string">"text/html; charset=utf-8"</span> /&gt;</span></span><br><span class="line">    <span class="tag">&lt;<span class="name">title</span>&gt;</span>在线生成红黑树（含变形步骤）<span class="tag">&lt;/<span class="name">title</span>&gt;</span></span><br><span class="line"><span class="tag">&lt;/<span class="name">head</span>&gt;</span></span><br><span class="line"><span class="tag">&lt;<span class="name">body</span>&gt;</span></span><br><span class="line">    <span class="tag">&lt;<span class="name">div</span>&gt;</span></span><br><span class="line">        <span class="tag">&lt;<span class="name">ul</span>&gt;</span></span><br><span class="line">            <span class="tag">&lt;<span class="name">li</span>&gt;</span>增加节点<span class="tag">&lt;/<span class="name">li</span>&gt;</span></span><br><span class="line">            <span class="tag">&lt;<span class="name">li</span>&gt;</span>方式一：<span class="tag">&lt;<span class="name">input</span> <span class="attr">type</span>=<span class="string">"button"</span> <span class="attr">value</span>=<span class="string">"随机增加一个节点"</span> <span class="attr">title</span>=<span class="string">"随机增加一个节点"</span> <span class="attr">onclick</span>=<span class="string">"AddRandom()"</span> /&gt;</span><span class="tag">&lt;/<span class="name">li</span>&gt;</span></span><br><span class="line">            <span class="tag">&lt;<span class="name">li</span>&gt;</span>方式二：<span class="tag">&lt;<span class="name">input</span> <span class="attr">id</span>=<span class="string">"numbertext"</span> <span class="attr">title</span>=<span class="string">""</span> <span class="attr">placeholder</span>=<span class="string">"请用,(单字节)分割数字,0-999之间的数字"</span> <span class="attr">value</span>=<span class="string">""</span> /&gt;</span><span class="tag">&lt;<span class="name">input</span> <span class="attr">type</span>=<span class="string">"button"</span> <span class="attr">value</span>=<span class="string">"一个一个节点增加"</span> <span class="attr">title</span>=<span class="string">"增加一个节点"</span> <span class="attr">onclick</span>=<span class="string">"AddOneNumber()"</span> /&gt;</span><span class="tag">&lt;/<span class="name">li</span>&gt;</span></span><br><span class="line">            <span class="tag">&lt;<span class="name">li</span>&gt;</span><span class="tag">&lt;/<span class="name">li</span>&gt;</span></span><br><span class="line">            <span class="tag">&lt;<span class="name">li</span>&gt;</span>删除节点<span class="tag">&lt;/<span class="name">li</span>&gt;</span></span><br><span class="line">            <span class="tag">&lt;<span class="name">li</span>&gt;</span><span class="tag">&lt;<span class="name">input</span> <span class="attr">id</span>=<span class="string">"deleteNumberText"</span> <span class="attr">type</span>=<span class="string">"text"</span> <span class="attr">placeholder</span>=<span class="string">"请输入需要删除的节点"</span> /&gt;</span><span class="tag">&lt;<span class="name">input</span> <span class="attr">type</span>=<span class="string">"button"</span> <span class="attr">value</span>=<span class="string">"删除"</span> <span class="attr">onclick</span>=<span class="string">"DeleteNumber()"</span> /&gt;</span> <span class="tag">&lt;/<span class="name">li</span>&gt;</span></span><br><span class="line">            <span class="tag">&lt;<span class="name">li</span>&gt;</span><span class="tag">&lt;/<span class="name">li</span>&gt;</span></span><br><span class="line">            <span class="tag">&lt;<span class="name">li</span>&gt;</span>参考：  http://www.cnblogs.com/skywang12345/p/3603935.html <span class="tag">&lt;/<span class="name">li</span>&gt;</span></span><br><span class="line">        <span class="tag">&lt;/<span class="name">ul</span>&gt;</span></span><br><span class="line">    <span class="tag">&lt;/<span class="name">div</span>&gt;</span></span><br><span class="line">    <span class="tag">&lt;<span class="name">form</span>&gt;</span></span><br><span class="line">        <span class="tag">&lt;<span class="name">fieldset</span>&gt;</span></span><br><span class="line">            <span class="tag">&lt;<span class="name">legend</span>&gt;</span>红黑树<span class="tag">&lt;/<span class="name">legend</span>&gt;</span></span><br><span class="line">            <span class="tag">&lt;<span class="name">div</span> <span class="attr">id</span>=<span class="string">"currentView"</span>&gt;</span><span class="tag">&lt;/<span class="name">div</span>&gt;</span></span><br><span class="line">        <span class="tag">&lt;/<span class="name">fieldset</span>&gt;</span></span><br><span class="line">    <span class="tag">&lt;/<span class="name">form</span>&gt;</span></span><br><span class="line">    <span class="tag">&lt;<span class="name">form</span> <span class="attr">id</span>=<span class="string">"stepView"</span>&gt;</span><span class="tag">&lt;/<span class="name">form</span>&gt;</span></span><br><span class="line"> <span class="comment">&lt;!--我的博客： http://www.cnblogs.com/bbvi/ --&gt;</span> </span><br><span class="line">    </span><br><span class="line">    <span class="tag">&lt;<span class="name">script</span>&gt;</span></span><br><span class="line"><span class="actionscript">        <span class="keyword">var</span> NodeColor = &#123; Black: <span class="string">"black"</span>, Red: <span class="string">"red"</span> &#125;;</span></span><br><span class="line"></span><br><span class="line"><span class="actionscript">        <span class="keyword">var</span> RBNode = <span class="function"><span class="keyword">function</span> <span class="params">(_date, _paret, _color)</span> </span>&#123;</span></span><br><span class="line"><span class="actionscript">            <span class="keyword">this</span>.Data = _date;</span></span><br><span class="line"><span class="actionscript">            <span class="keyword">this</span>.Parent = _paret;</span></span><br><span class="line"><span class="actionscript">            <span class="keyword">this</span>.Color = _color;</span></span><br><span class="line"><span class="actionscript">            <span class="keyword">this</span>.LeftNode = <span class="literal">null</span>;</span></span><br><span class="line"><span class="actionscript">            <span class="keyword">this</span>.RightNode = <span class="literal">null</span>;</span></span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">        <span class="keyword">var</span> RedBlackBinaryTree = <span class="function"><span class="keyword">function</span> <span class="params">()</span> </span>&#123;</span></span><br><span class="line"><span class="actionscript">            <span class="keyword">this</span>.RootNode = <span class="literal">null</span>;<span class="comment">//根节点</span></span></span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="keyword">this</span>.Insert = <span class="function"><span class="keyword">function</span> <span class="params">(insertValue)</span> </span>&#123;</span></span><br><span class="line"><span class="actionscript">                <span class="keyword">if</span> (<span class="keyword">this</span>.RootNode == <span class="literal">null</span>) &#123;</span></span><br><span class="line"><span class="actionscript">                    <span class="keyword">this</span>.RootNode = <span class="keyword">new</span> RBNode(insertValue, <span class="literal">null</span>, NodeColor.Black);</span></span><br><span class="line"><span class="actionscript">                &#125; <span class="keyword">else</span> &#123;</span></span><br><span class="line"><span class="actionscript">                    <span class="keyword">var</span> newNode = insert.call(<span class="keyword">this</span>, insertValue);</span></span><br><span class="line"><span class="actionscript">                    insertFixUp.call(<span class="keyword">this</span>, newNode);</span></span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="function"><span class="keyword">function</span> <span class="title">insert</span><span class="params">(key)</span> </span>&#123;</span></span><br><span class="line"><span class="actionscript">                ClearStepView();<span class="comment">//清空分解步骤</span></span></span><br><span class="line"><span class="actionscript">                <span class="keyword">var</span> node = <span class="keyword">this</span>.RootNode;</span></span><br><span class="line"></span><br><span class="line"><span class="actionscript">                <span class="keyword">var</span> newNode = <span class="keyword">new</span> RBNode(key, <span class="literal">null</span>, NodeColor.Red);</span></span><br><span class="line"><span class="actionscript">                <span class="keyword">while</span> (<span class="literal">true</span>) &#123;</span></span><br><span class="line">                    if (key &gt; node.Data) &#123;</span><br><span class="line"><span class="actionscript">                        <span class="keyword">if</span> (node.RightNode == <span class="literal">null</span>) &#123;</span></span><br><span class="line">                            newNode.Parent = node;</span><br><span class="line">                            node.RightNode = newNode;</span><br><span class="line"><span class="actionscript">                            <span class="keyword">break</span>;</span></span><br><span class="line">                        &#125;</span><br><span class="line">                        node = node.RightNode;</span><br><span class="line"><span class="actionscript">                    &#125; <span class="keyword">else</span> <span class="keyword">if</span> (key &lt; node.Data) &#123;</span></span><br><span class="line"><span class="actionscript">                        <span class="keyword">if</span> (node.LeftNode == <span class="literal">null</span>) &#123;</span></span><br><span class="line">                            newNode.Parent = node;</span><br><span class="line">                            node.LeftNode = newNode;</span><br><span class="line"><span class="actionscript">                            <span class="keyword">break</span>;</span></span><br><span class="line">                        &#125;</span><br><span class="line">                        node = node.LeftNode;</span><br><span class="line"><span class="actionscript">                    &#125; <span class="keyword">else</span> &#123;</span></span><br><span class="line"><span class="actionscript">                        <span class="keyword">break</span>;</span></span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line"><span class="actionscript">                <span class="keyword">return</span> newNode;</span></span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="function"><span class="keyword">function</span> <span class="title">insertFixUp</span><span class="params">(node)</span> </span>&#123;</span></span><br><span class="line"><span class="actionscript">                <span class="keyword">var</span> parentNode = node.Parent;</span></span><br><span class="line"><span class="actionscript">                <span class="keyword">if</span> (parentNode != <span class="literal">null</span> &amp;&amp; NodeColor.Red == parentNode.Color) &#123;</span></span><br><span class="line"><span class="actionscript">                    <span class="keyword">var</span> gprentNode = parentNode.Parent;</span></span><br><span class="line">                    if (parentNode == gprentNode.LeftNode) &#123;</span><br><span class="line"><span class="actionscript">                        <span class="keyword">var</span> uncleNode = gprentNode.RightNode;</span></span><br><span class="line"><span class="actionscript">                        <span class="keyword">if</span> (uncleNode != <span class="literal">null</span> &amp;&amp; NodeColor.Red == uncleNode.Color) &#123;</span></span><br><span class="line"><span class="actionscript">                            CreateStepView(<span class="keyword">this</span>.RootNode, <span class="string">"insertCaseA1"</span>, node.Data);<span class="comment">//记录分解步骤</span></span></span><br><span class="line">                            parentNode.Color = NodeColor.Black;</span><br><span class="line">                            uncleNode.Color = NodeColor.Black;</span><br><span class="line">                            gprentNode.Color = NodeColor.Red;</span><br><span class="line"><span class="actionscript">                            CreateStepView(<span class="keyword">this</span>.RootNode, <span class="string">"insertSolutionA1"</span>);<span class="comment">//记录分解步骤</span></span></span><br><span class="line"><span class="actionscript">                            insertFixUp.call(<span class="keyword">this</span>, gprentNode);</span></span><br><span class="line"><span class="actionscript">                        &#125; <span class="keyword">else</span> &#123;</span></span><br><span class="line">                            if (parentNode.RightNode == node) &#123;</span><br><span class="line"><span class="actionscript">                                CreateStepView(<span class="keyword">this</span>.RootNode, <span class="string">"insertCaseB1"</span>, node.Data);<span class="comment">//记录分解步骤</span></span></span><br><span class="line"><span class="actionscript">                                leftRotation.call(<span class="keyword">this</span>, parentNode);</span></span><br><span class="line"><span class="actionscript">                                CreateStepView(<span class="keyword">this</span>.RootNode, <span class="string">"insertSolutionB1"</span>);<span class="comment">//记录分解步骤</span></span></span><br><span class="line"><span class="actionscript">                                insertFixUp.call(<span class="keyword">this</span>, parentNode);</span></span><br><span class="line"><span class="actionscript">                            &#125; <span class="keyword">else</span> <span class="keyword">if</span> (parentNode.LeftNode == node) &#123;</span></span><br><span class="line"><span class="actionscript">                                CreateStepView(<span class="keyword">this</span>.RootNode, <span class="string">"insertCase3"</span>, node.Data);<span class="comment">//记录分解步骤</span></span></span><br><span class="line">                                parentNode.Color = NodeColor.Black;</span><br><span class="line">                                gprentNode.Color = NodeColor.Red;</span><br><span class="line"><span class="actionscript">                                rightRotation.call(<span class="keyword">this</span>, gprentNode);</span></span><br><span class="line"><span class="actionscript">                                CreateStepView(<span class="keyword">this</span>.RootNode, <span class="string">"insertSolution3"</span>);<span class="comment">//记录分解步骤</span></span></span><br><span class="line">                            &#125;</span><br><span class="line">                        &#125;</span><br><span class="line"><span class="actionscript">                    &#125; <span class="keyword">else</span> &#123;</span></span><br><span class="line"><span class="actionscript">                        <span class="keyword">var</span> uncleNode = gprentNode.LeftNode;</span></span><br><span class="line"><span class="actionscript">                        <span class="keyword">if</span> (uncleNode != <span class="literal">null</span> &amp;&amp; NodeColor.Red == uncleNode.Color) &#123;</span></span><br><span class="line"><span class="actionscript">                            CreateStepView(<span class="keyword">this</span>.RootNode, <span class="string">"insertCaseA1"</span>, node.Data);<span class="comment">//记录分解步骤</span></span></span><br><span class="line">                            parentNode.Color = NodeColor.Black;</span><br><span class="line">                            uncleNode.Color = NodeColor.Black;</span><br><span class="line">                            gprentNode.Color = NodeColor.Red;</span><br><span class="line"><span class="actionscript">                            CreateStepView(<span class="keyword">this</span>.RootNode, <span class="string">"insertSolutionA1"</span>);<span class="comment">//记录分解步骤</span></span></span><br><span class="line"><span class="actionscript">                            insertFixUp.call(<span class="keyword">this</span>, gprentNode);</span></span><br><span class="line"><span class="actionscript">                        &#125; <span class="keyword">else</span> &#123;</span></span><br><span class="line">                            if (parentNode.LeftNode == node) &#123;</span><br><span class="line"><span class="actionscript">                                CreateStepView(<span class="keyword">this</span>.RootNode, <span class="string">"insertCase4"</span>, node.Data);<span class="comment">//记录分解步骤</span></span></span><br><span class="line"><span class="actionscript">                                rightRotation.call(<span class="keyword">this</span>, parentNode);</span></span><br><span class="line"><span class="actionscript">                                CreateStepView(<span class="keyword">this</span>.RootNode, <span class="string">"insertSolution4"</span>);<span class="comment">//记录分解步骤</span></span></span><br><span class="line"><span class="actionscript">                                insertFixUp.call(<span class="keyword">this</span>, parentNode);</span></span><br><span class="line"><span class="actionscript">                            &#125; <span class="keyword">else</span> <span class="keyword">if</span> (parentNode.RightNode == node) &#123;</span></span><br><span class="line"><span class="actionscript">                                CreateStepView(<span class="keyword">this</span>.RootNode, <span class="string">"insertCase5"</span>, node.Data);<span class="comment">//记录分解步骤</span></span></span><br><span class="line">                                parentNode.Color = NodeColor.Black;</span><br><span class="line">                                gprentNode.Color = NodeColor.Red;</span><br><span class="line"><span class="actionscript">                                leftRotation.call(<span class="keyword">this</span>, gprentNode);</span></span><br><span class="line"><span class="actionscript">                                CreateStepView(<span class="keyword">this</span>.RootNode, <span class="string">"insertSolution5"</span>);<span class="comment">//记录分解步骤</span></span></span><br><span class="line">                            &#125;</span><br><span class="line">                        &#125;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line"><span class="actionscript">                <span class="keyword">this</span>.RootNode.Color = NodeColor.Black;</span></span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="function"><span class="keyword">function</span> <span class="title">leftRotation</span><span class="params">(node)</span> </span>&#123;</span></span><br><span class="line"><span class="actionscript">                <span class="keyword">var</span> temp = node.RightNode;</span></span><br><span class="line"></span><br><span class="line">                node.RightNode = temp.LeftNode;</span><br><span class="line"><span class="actionscript">                <span class="keyword">if</span> (temp.LeftNode != <span class="literal">null</span>) &#123;</span></span><br><span class="line">                    temp.LeftNode.Parent = node;</span><br><span class="line">                &#125;</span><br><span class="line"></span><br><span class="line">                temp.Parent = node.Parent;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">                <span class="keyword">if</span> (node.Parent == <span class="literal">null</span>) &#123;</span></span><br><span class="line"><span class="actionscript">                    <span class="keyword">this</span>.RootNode = temp;</span></span><br><span class="line">                &#125;</span><br><span class="line"><span class="actionscript">                <span class="keyword">else</span> &#123;</span></span><br><span class="line">                    if (node.Parent.LeftNode == node) &#123;</span><br><span class="line">                        node.Parent.LeftNode = temp;</span><br><span class="line"><span class="actionscript">                    &#125; <span class="keyword">else</span> &#123;</span></span><br><span class="line">                        node.Parent.RightNode = temp;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">                temp.LeftNode = node;</span><br><span class="line">                node.Parent = temp;</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="function"><span class="keyword">function</span> <span class="title">rightRotation</span><span class="params">(node)</span> </span>&#123;</span></span><br><span class="line"><span class="actionscript">                <span class="keyword">var</span> temp = node.LeftNode;</span></span><br><span class="line"></span><br><span class="line">                node.LeftNode = temp.RightNode;</span><br><span class="line"><span class="actionscript">                <span class="keyword">if</span> (temp.RightNode != <span class="literal">null</span>) &#123;</span></span><br><span class="line">                    temp.RightNode.Parent = node;</span><br><span class="line">                &#125;</span><br><span class="line"></span><br><span class="line">                temp.Parent = node.Parent;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">                <span class="keyword">if</span> (node.Parent == <span class="literal">null</span>) &#123;</span></span><br><span class="line"><span class="actionscript">                    <span class="keyword">this</span>.RootNode = temp;</span></span><br><span class="line"><span class="actionscript">                &#125; <span class="keyword">else</span> &#123;</span></span><br><span class="line">                    if (node == node.Parent.RightNode) &#123;</span><br><span class="line">                        node.Parent.RightNode = temp;</span><br><span class="line"><span class="actionscript">                    &#125; <span class="keyword">else</span> &#123;</span></span><br><span class="line">                        node.Parent.LeftNode = temp;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">                temp.RightNode = node;</span><br><span class="line">                node.Parent = temp;</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="keyword">this</span>.Remove = <span class="function"><span class="keyword">function</span> <span class="params">(key)</span> </span>&#123;</span></span><br><span class="line"><span class="actionscript">                <span class="keyword">var</span> node = search.call(<span class="keyword">this</span>, <span class="keyword">this</span>.RootNode, key);</span></span><br><span class="line"><span class="actionscript">                <span class="keyword">if</span> (node == <span class="literal">null</span>) &#123;</span></span><br><span class="line"><span class="actionscript">                    <span class="keyword">return</span>;</span></span><br><span class="line"><span class="actionscript">                &#125; <span class="keyword">else</span> &#123;</span></span><br><span class="line"><span class="actionscript">                    remove.call(<span class="keyword">this</span>, node);</span></span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="function"><span class="keyword">function</span> <span class="title">remove</span><span class="params">(node)</span> </span>&#123;</span></span><br><span class="line"><span class="actionscript">                ClearStepView();<span class="comment">//清空分解步骤</span></span></span><br><span class="line">                </span><br><span class="line"><span class="actionscript">                <span class="keyword">var</span> child, parent, nodeColor;</span></span><br><span class="line"><span class="actionscript">                <span class="keyword">if</span> (node.LeftNode != <span class="literal">null</span> &amp;&amp; node.RightNode != <span class="literal">null</span>) &#123;</span></span><br><span class="line"><span class="actionscript">                    CreateStepView(<span class="keyword">this</span>.RootNode, <span class="string">"deleteCase8"</span>, node.Data);<span class="comment">//记录分解步骤</span></span></span><br><span class="line"><span class="actionscript">                    <span class="keyword">var</span> tempNode = findMin(node.RightNode);</span></span><br><span class="line"><span class="actionscript">                    <span class="keyword">if</span> (node.Parent == <span class="literal">null</span>) &#123;</span></span><br><span class="line"><span class="actionscript">                        <span class="keyword">this</span>.RootNode = tempNode;</span></span><br><span class="line"><span class="actionscript">                    &#125; <span class="keyword">else</span> &#123;</span></span><br><span class="line">                        if (node.Parent.LeftNode == node) &#123;</span><br><span class="line">                            node.Parent.LeftNode = tempNode;</span><br><span class="line"><span class="actionscript">                        &#125; <span class="keyword">else</span> &#123;</span></span><br><span class="line">                            node.Parent.RightNode = tempNode;</span><br><span class="line">                        &#125;</span><br><span class="line">                    &#125;</span><br><span class="line"></span><br><span class="line">                    child = tempNode.RightNode;</span><br><span class="line">                    parent = tempNode.Parent;</span><br><span class="line">                    nodeColor = tempNode.Color;</span><br><span class="line"></span><br><span class="line">                    if (parent.Data == node.Data) &#123;</span><br><span class="line">                        parent = tempNode;</span><br><span class="line"><span class="actionscript">                    &#125; <span class="keyword">else</span> &#123;</span></span><br><span class="line"><span class="actionscript">                        <span class="keyword">if</span> (child != <span class="literal">null</span>) &#123;</span></span><br><span class="line">                            child.Parent = parent;</span><br><span class="line">                        &#125;</span><br><span class="line">                        parent.LeftNode = child;</span><br><span class="line"></span><br><span class="line">                        tempNode.RightNode = node.RightNode;</span><br><span class="line">                        node.RightNode.Parent = tempNode;</span><br><span class="line">                    &#125;</span><br><span class="line"></span><br><span class="line">                    tempNode.Parent = node.Parent;</span><br><span class="line">                    tempNode.Color = node.Color;</span><br><span class="line">                    tempNode.LeftNode = node.LeftNode</span><br><span class="line">                    node.LeftNode.Parent = tempNode;</span><br><span class="line">                    </span><br><span class="line"><span class="actionscript">                    CreateStepView(<span class="keyword">this</span>.RootNode, <span class="string">"deleteSolution8"</span>);<span class="comment">//记录分解步骤</span></span></span><br><span class="line"></span><br><span class="line">                    if (nodeColor == NodeColor.Black) &#123;</span><br><span class="line"><span class="actionscript">                        removeFixUp.call(<span class="keyword">this</span>, child, parent);</span></span><br><span class="line">                    &#125;</span><br><span class="line"><span class="actionscript">                &#125; <span class="keyword">else</span> &#123;</span></span><br><span class="line"><span class="actionscript">                    CreateStepView(<span class="keyword">this</span>.RootNode, <span class="string">"deleteCase9"</span>, node.Data);<span class="comment">//记录分解步骤</span></span></span><br><span class="line"><span class="actionscript">                    <span class="keyword">if</span> (node.LeftNode != <span class="literal">null</span>) &#123;</span></span><br><span class="line">                        child = node.LeftNode;</span><br><span class="line"><span class="actionscript">                    &#125; <span class="keyword">else</span> &#123;</span></span><br><span class="line">                        child = node.RightNode;</span><br><span class="line">                    &#125;</span><br><span class="line"></span><br><span class="line">                    parent = node.Parent;</span><br><span class="line">                    nodeColor = node.Color;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">                    <span class="keyword">if</span> (child != <span class="literal">null</span>) &#123;</span></span><br><span class="line">                        child.Parent = parent;</span><br><span class="line">                    &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">                    <span class="keyword">if</span> (parent != <span class="literal">null</span>) &#123;</span></span><br><span class="line"><span class="actionscript">                        <span class="keyword">if</span> (parent.LeftNode != <span class="literal">null</span> &amp;&amp; parent.LeftNode.Data == node.Data) &#123;</span></span><br><span class="line">                            parent.LeftNode = child;</span><br><span class="line"><span class="actionscript">                        &#125; <span class="keyword">else</span> &#123;</span></span><br><span class="line">                            parent.RightNode = child;</span><br><span class="line">                        &#125;</span><br><span class="line"><span class="actionscript">                    &#125; <span class="keyword">else</span> &#123;</span></span><br><span class="line"><span class="actionscript">                        <span class="keyword">this</span>.RootNode = child;</span></span><br><span class="line">                    &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">                    CreateStepView(<span class="keyword">this</span>.RootNode, <span class="string">"deleteSolution9"</span>);<span class="comment">//记录分解步骤</span></span></span><br><span class="line"></span><br><span class="line">                    if (nodeColor == NodeColor.Black) &#123;</span><br><span class="line"><span class="actionscript">                        removeFixUp.call(<span class="keyword">this</span>, child, parent)</span></span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line"><span class="actionscript">                node = <span class="literal">null</span>;</span></span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="function"><span class="keyword">function</span> <span class="title">removeFixUp</span><span class="params">(node, parentNode)</span> </span>&#123;</span></span><br><span class="line">                </span><br><span class="line"><span class="actionscript">                <span class="keyword">var</span> otherNode;</span></span><br><span class="line"><span class="actionscript">                <span class="keyword">while</span> ((node == <span class="literal">null</span> || node.Color == NodeColor.Black) &amp;&amp; (node != <span class="keyword">this</span>.RootNode)) &#123;</span></span><br><span class="line">                    if (parentNode.LeftNode == node) &#123;</span><br><span class="line">                        otherNode = parentNode.RightNode;</span><br><span class="line">                        if (otherNode.Color == NodeColor.Red) &#123;</span><br><span class="line"><span class="actionscript">                            CreateStepView(<span class="keyword">this</span>.RootNode, <span class="string">"deleteCase1"</span>);<span class="comment">//记录分解步骤</span></span></span><br><span class="line">                            otherNode.Color = NodeColor.Black;</span><br><span class="line">                            parentNode.Color = NodeColor.Red;</span><br><span class="line"><span class="actionscript">                            leftRotation.call(<span class="keyword">this</span>, parentNode);</span></span><br><span class="line">                            otherNode = parentNode.RightNode;</span><br><span class="line"><span class="actionscript">                            CreateStepView(<span class="keyword">this</span>.RootNode, <span class="string">"deleteSolution1"</span>);<span class="comment">//记录分解步骤</span></span></span><br><span class="line">                        &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">                        <span class="keyword">if</span> ((otherNode.LeftNode == <span class="literal">null</span> || otherNode.LeftNode.Color == NodeColor.Black) &amp;&amp;</span></span><br><span class="line"><span class="actionscript">                           (otherNode.RightNode == <span class="literal">null</span> || otherNode.RightNode.Color == NodeColor.Black)) &#123;</span></span><br><span class="line"><span class="actionscript">                            CreateStepView(<span class="keyword">this</span>.RootNode, <span class="string">"deleteCase3"</span>);<span class="comment">//记录分解步骤</span></span></span><br><span class="line">                            otherNode.Color = NodeColor.Red;</span><br><span class="line">                            node = parentNode;</span><br><span class="line">                            parentNode = node.Parent;</span><br><span class="line"><span class="actionscript">                            CreateStepView(<span class="keyword">this</span>.RootNode, <span class="string">"deleteSolution3"</span>);<span class="comment">//记录分解步骤</span></span></span><br><span class="line"><span class="actionscript">                        &#125; <span class="keyword">else</span> &#123;</span></span><br><span class="line"><span class="actionscript">                            <span class="keyword">if</span> (otherNode.RightNode == <span class="literal">null</span> || otherNode.RightNode.Color == NodeColor.Black) &#123;</span></span><br><span class="line"><span class="actionscript">                                CreateStepView(<span class="keyword">this</span>.RootNode, <span class="string">"deleteCase4"</span>);<span class="comment">//记录分解步骤</span></span></span><br><span class="line">                                otherNode.LeftNode.Color == NodeColor.Black;</span><br><span class="line">                                otherNode.Color = NodeColor.Red;</span><br><span class="line"><span class="actionscript">                                rightRotation.call(<span class="keyword">this</span>, otherNode);</span></span><br><span class="line">                                otherNode = parentNode.RightNode;</span><br><span class="line"><span class="actionscript">                                CreateStepView(<span class="keyword">this</span>.RootNode, <span class="string">"deleteSolution4"</span>);<span class="comment">//记录分解步骤</span></span></span><br><span class="line">                            &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">                            CreateStepView(<span class="keyword">this</span>.RootNode, <span class="string">"deleteCase6"</span>);<span class="comment">//记录分解步骤</span></span></span><br><span class="line">                            otherNode.Color = parentNode.Color;</span><br><span class="line">                            parentNode.Color = NodeColor.Black;</span><br><span class="line">                            otherNode.RightNode.Color = NodeColor.Black;</span><br><span class="line"><span class="actionscript">                            leftRotation.call(<span class="keyword">this</span>, parentNode);</span></span><br><span class="line"><span class="actionscript">                            node = <span class="keyword">this</span>.RootNode;</span></span><br><span class="line"><span class="actionscript">                            CreateStepView(<span class="keyword">this</span>.RootNode, <span class="string">"deleteSolution6"</span>);<span class="comment">//记录分解步骤</span></span></span><br><span class="line"><span class="actionscript">                            <span class="keyword">break</span>;</span></span><br><span class="line">                        &#125;</span><br><span class="line"><span class="actionscript">                    &#125; <span class="keyword">else</span> &#123;</span></span><br><span class="line">                        otherNode = parentNode.LeftNode;</span><br><span class="line">                        if (otherNode.Color == NodeColor.Red) &#123;</span><br><span class="line"><span class="actionscript">                            CreateStepView(<span class="keyword">this</span>.RootNode, <span class="string">"deleteCase2"</span>);<span class="comment">//记录分解步骤</span></span></span><br><span class="line">                            otherNode.Color = NodeColor.Black;</span><br><span class="line">                            parentNode.Color = NodeColor.Red;</span><br><span class="line"><span class="actionscript">                            rightRotation.call(<span class="keyword">this</span>, parentNode);</span></span><br><span class="line">                            otherNode = parentNode.LeftNode;</span><br><span class="line"><span class="actionscript">                            CreateStepView(<span class="keyword">this</span>.RootNode, <span class="string">"deleteSolution2"</span>);<span class="comment">//记录分解步骤</span></span></span><br><span class="line">                        &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">                        <span class="keyword">if</span> ((otherNode.LeftNode == <span class="literal">null</span> || otherNode.LeftNode.Color == NodeColor.Black) &amp;&amp;</span></span><br><span class="line"><span class="actionscript">                            (otherNode.RightNode == <span class="literal">null</span> || otherNode.RightNode.Color == NodeColor.Black)) &#123;</span></span><br><span class="line"><span class="actionscript">                            CreateStepView(<span class="keyword">this</span>.RootNode, <span class="string">"deleteCase3"</span>);<span class="comment">//记录分解步骤</span></span></span><br><span class="line">                            otherNode.Color = NodeColor.Red;</span><br><span class="line">                            node = parentNode;</span><br><span class="line">                            parentNode = node.parent;</span><br><span class="line"><span class="actionscript">                            CreateStepView(<span class="keyword">this</span>.RootNode, <span class="string">"deleteSolution3"</span>);<span class="comment">//记录分解步骤</span></span></span><br><span class="line"><span class="actionscript">                        &#125; <span class="keyword">else</span> &#123;</span></span><br><span class="line"><span class="actionscript">                            <span class="keyword">if</span> (otherNode.LeftNode == <span class="literal">null</span> || otherNode.LeftNode.Color == NodeColor.Black) &#123;</span></span><br><span class="line"><span class="actionscript">                                CreateStepView(<span class="keyword">this</span>.RootNode, <span class="string">"deleteCase5"</span>);<span class="comment">//记录分解步骤</span></span></span><br><span class="line">                                otherNode.RightNode.Color = NodeColor.Black;</span><br><span class="line">                                otherNode.Color = NodeColor.Red;</span><br><span class="line"><span class="actionscript">                                leftRotation.call(<span class="keyword">this</span>, otherNode);</span></span><br><span class="line">                                otherNode = parentNode.LeftNode;</span><br><span class="line"><span class="actionscript">                                CreateStepView(<span class="keyword">this</span>.RootNode, <span class="string">"deleteSolution5"</span>);<span class="comment">//记录分解步骤</span></span></span><br><span class="line">                            &#125;</span><br><span class="line"><span class="actionscript">                            CreateStepView(<span class="keyword">this</span>.RootNode, <span class="string">"deleteCase7"</span>);<span class="comment">//记录分解步骤</span></span></span><br><span class="line">                            otherNode.Color = parentNode.Color;</span><br><span class="line">                            parentNode.Color = NodeColor.Black;</span><br><span class="line">                            otherNode.LeftNode.Color = NodeColor.Black;</span><br><span class="line"><span class="actionscript">                            rightRotation.call(<span class="keyword">this</span>, parentNode);</span></span><br><span class="line"><span class="actionscript">                            node = <span class="keyword">this</span>.RootNode;</span></span><br><span class="line"><span class="actionscript">                            CreateStepView(<span class="keyword">this</span>.RootNode, <span class="string">"deleteSolution7"</span>);<span class="comment">//记录分解步骤</span></span></span><br><span class="line"><span class="actionscript">                            <span class="keyword">break</span>;</span></span><br><span class="line">                        &#125;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line"><span class="actionscript">                <span class="keyword">if</span> (node != <span class="literal">null</span>) &#123;</span></span><br><span class="line">                    node.Color = NodeColor.Black;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="keyword">this</span>.Search = <span class="function"><span class="keyword">function</span> <span class="params">(key)</span> </span>&#123;</span></span><br><span class="line"><span class="actionscript">                <span class="keyword">return</span> search.call(<span class="keyword">this</span>, <span class="keyword">this</span>.RootNode, key);</span></span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="function"><span class="keyword">function</span> <span class="title">search</span><span class="params">(node, key)</span> </span>&#123;</span></span><br><span class="line"><span class="actionscript">                <span class="keyword">if</span> (node == <span class="literal">null</span>) &#123;</span></span><br><span class="line"><span class="actionscript">                    <span class="keyword">return</span> <span class="literal">null</span>;</span></span><br><span class="line">                &#125;</span><br><span class="line"></span><br><span class="line">                if (node.Data &gt; key) &#123;</span><br><span class="line"><span class="actionscript">                    <span class="keyword">return</span> search(node.LeftNode, key);</span></span><br><span class="line"><span class="actionscript">                &#125; <span class="keyword">else</span> <span class="keyword">if</span> (node.Data &lt; key) &#123;</span></span><br><span class="line"><span class="actionscript">                    <span class="keyword">return</span> search(node.RightNode, key);</span></span><br><span class="line"><span class="actionscript">                &#125; <span class="keyword">else</span> &#123;</span></span><br><span class="line"><span class="actionscript">                    <span class="keyword">return</span> node;</span></span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="keyword">this</span>.FindMin = <span class="function"><span class="keyword">function</span> <span class="params">()</span> </span>&#123;</span></span><br><span class="line"><span class="actionscript">                <span class="keyword">return</span> findMin(<span class="keyword">this</span>.RootNode);</span></span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="function"><span class="keyword">function</span> <span class="title">findMin</span><span class="params">(node)</span> </span>&#123;</span></span><br><span class="line"><span class="actionscript">                <span class="keyword">if</span> (node.LeftNode == <span class="literal">null</span>) &#123;</span></span><br><span class="line"><span class="actionscript">                    <span class="keyword">return</span> node;</span></span><br><span class="line">                &#125;</span><br><span class="line"><span class="actionscript">                <span class="keyword">return</span> findMin(node.LeftNode);</span></span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="keyword">this</span>.FindMax = <span class="function"><span class="keyword">function</span> <span class="params">()</span> </span>&#123;</span></span><br><span class="line"><span class="actionscript">                <span class="keyword">return</span> findMax(<span class="keyword">this</span>.RootNode)</span></span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="function"><span class="keyword">function</span> <span class="title">findMax</span><span class="params">(node)</span> </span>&#123;</span></span><br><span class="line"><span class="actionscript">                <span class="keyword">if</span> (node.RightNode == <span class="literal">null</span>) &#123;</span></span><br><span class="line"><span class="actionscript">                    <span class="keyword">return</span> node;</span></span><br><span class="line">                &#125;</span><br><span class="line"><span class="actionscript">                <span class="keyword">return</span> findMax(node.RightNode);</span></span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="keyword">this</span>.SearchRange = <span class="function"><span class="keyword">function</span> <span class="params">(minKey, maxKey)</span> </span>&#123;</span></span><br><span class="line"><span class="actionscript">                <span class="keyword">return</span> searchRange(minKey, maxKey, <span class="keyword">this</span>.RootNode, []);</span></span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="function"><span class="keyword">function</span> <span class="title">searchRange</span><span class="params">(minKey, maxKey, node, nodeList)</span> </span>&#123;</span></span><br><span class="line"><span class="actionscript">                <span class="keyword">if</span> (node == <span class="literal">null</span>) &#123;</span></span><br><span class="line"><span class="actionscript">                    <span class="keyword">return</span> nodeList;</span></span><br><span class="line">                &#125;</span><br><span class="line"></span><br><span class="line">                if (node.Data &gt; minKey) &#123;</span><br><span class="line">                    searchRange(minKey, maxKey, node.LeftNode, nodeList);</span><br><span class="line">                &#125;</span><br><span class="line"></span><br><span class="line">                if (node.Data &gt;= minKey &amp;&amp; node.Data &lt; maxKey) &#123;</span><br><span class="line">                    nodeList.push(node.Data);</span><br><span class="line">                &#125;</span><br><span class="line"></span><br><span class="line">                if (node.Data &lt; maxKey) &#123;</span><br><span class="line">                    searchRange(minKey, maxKey, node.RightNode, nodeList);</span><br><span class="line">                &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">                <span class="keyword">return</span> nodeList;</span></span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="keyword">this</span>.LevelOrder = <span class="function"><span class="keyword">function</span> <span class="params">(action)</span> </span>&#123;</span></span><br><span class="line"><span class="actionscript">                levelOrder(<span class="keyword">this</span>.RootNode, action);</span></span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="function"><span class="keyword">function</span> <span class="title">levelOrder</span><span class="params">(node, action)</span> </span>&#123;</span></span><br><span class="line"><span class="actionscript">                <span class="keyword">var</span> stack = [];</span></span><br><span class="line">                stack.push(node);</span><br><span class="line"></span><br><span class="line"><span class="actionscript">                <span class="keyword">while</span> (stack.length &gt; <span class="number">0</span>) &#123;</span></span><br><span class="line"><span class="actionscript">                    <span class="keyword">var</span> temp = stack.pop();</span></span><br><span class="line"></span><br><span class="line">                    action(temp);</span><br><span class="line"></span><br><span class="line"><span class="actionscript">                    <span class="keyword">if</span> (temp.LeftNode != <span class="literal">null</span>) &#123;</span></span><br><span class="line">                        stack.push(temp.LeftNode);</span><br><span class="line">                    &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">                    <span class="keyword">if</span> (temp.RightNode != <span class="literal">null</span>) &#123;</span></span><br><span class="line">                        stack.push(temp.RightNode);</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="keyword">this</span>.PreOrder = <span class="function"><span class="keyword">function</span> <span class="params">(action)</span> </span>&#123;</span></span><br><span class="line"><span class="actionscript">                treeOrder(<span class="keyword">this</span>.RootNode, action, <span class="literal">null</span>, <span class="literal">null</span>);</span></span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="keyword">this</span>.InOrder = <span class="function"><span class="keyword">function</span> <span class="params">(action)</span> </span>&#123;</span></span><br><span class="line"><span class="actionscript">                treeOrder(<span class="keyword">this</span>.RootNode, <span class="literal">null</span>, action, <span class="literal">null</span>);</span></span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="keyword">this</span>.PostOrder = <span class="function"><span class="keyword">function</span> <span class="params">(action)</span> </span>&#123;</span></span><br><span class="line"><span class="actionscript">                treeOrder(<span class="keyword">this</span>.RootNode, <span class="literal">null</span>, <span class="literal">null</span>, action);</span></span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="function"><span class="keyword">function</span> <span class="title">treeOrder</span><span class="params">(node, preOrderAction, inOrderAction, postOrderAction)</span> </span>&#123;</span></span><br><span class="line">                if (preOrderAction) &#123;</span><br><span class="line">                    preOrderAction(node);</span><br><span class="line">                &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">                <span class="keyword">if</span> (node.LeftNode != <span class="literal">null</span>) &#123;</span></span><br><span class="line">                    treeOrder(node.LeftNode, preOrderAction, inOrderAction, postOrderAction);</span><br><span class="line">                &#125;</span><br><span class="line"></span><br><span class="line">                if (inOrderAction) &#123;</span><br><span class="line">                    inOrderAction(node);</span><br><span class="line">                &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">                <span class="keyword">if</span> (node.RightNode != <span class="literal">null</span>) &#123;</span></span><br><span class="line">                    treeOrder(node.RightNode, preOrderAction, inOrderAction, postOrderAction);</span><br><span class="line">                &#125;</span><br><span class="line"></span><br><span class="line">                if (postOrderAction) &#123;</span><br><span class="line">                    postOrderAction(node);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    <span class="tag">&lt;/<span class="name">script</span>&gt;</span></span><br><span class="line"></span><br><span class="line">    <span class="tag">&lt;<span class="name">script</span>&gt;</span></span><br><span class="line"><span class="actionscript">        <span class="keyword">var</span> height = <span class="number">50</span>;<span class="comment">//节点之间的高</span></span></span><br><span class="line"><span class="actionscript">        <span class="keyword">var</span> width = <span class="number">15</span>;<span class="comment">//节点之间的宽</span></span></span><br><span class="line"><span class="actionscript">        <span class="keyword">var</span> tops = <span class="number">40</span>;<span class="comment">//根节点离顶部的距离</span></span></span><br><span class="line"><span class="actionscript">        <span class="keyword">var</span> foot = <span class="number">40</span>;<span class="comment">//树离底部距离</span></span></span><br><span class="line"><span class="actionscript">        <span class="keyword">var</span> spacing = <span class="number">30</span>;<span class="comment">//树分别离两边的间距</span></span></span><br><span class="line"></span><br><span class="line"><span class="actionscript">        <span class="keyword">var</span> tree = <span class="keyword">new</span> RedBlackBinaryTree();</span></span><br><span class="line"></span><br><span class="line"><span class="actionscript">        <span class="function"><span class="keyword">function</span> <span class="title">AddOneNumber</span><span class="params">()</span> </span>&#123;</span></span><br><span class="line"><span class="javascript">            <span class="keyword">var</span> numbertext = <span class="built_in">document</span>.getElementById(<span class="string">"numbertext"</span>).value;</span></span><br><span class="line"></span><br><span class="line"><span class="javascript">            <span class="keyword">var</span> oneNums = numbertext.match(<span class="regexp">/[1-9][0-9]&#123;0,2&#125;\,?/</span>);</span></span><br><span class="line"><span class="javascript">            <span class="built_in">document</span>.getElementById(<span class="string">"numbertext"</span>).value = numbertext.replace(<span class="regexp">/[1-9][0-9]&#123;0,2&#125;\,?/</span>, <span class="string">""</span>);</span></span><br><span class="line"></span><br><span class="line"><span class="javascript">            <span class="keyword">var</span> num = (oneNums + <span class="string">""</span>).match(<span class="regexp">/[1-9][0-9]&#123;0,2&#125;/</span>);</span></span><br><span class="line"></span><br><span class="line">            if (!!num) &#123;</span><br><span class="line"><span class="javascript">                AddNumber(<span class="built_in">parseInt</span>(num));</span></span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">        <span class="function"><span class="keyword">function</span> <span class="title">AddRandom</span><span class="params">()</span> </span>&#123;</span></span><br><span class="line"><span class="javascript">            AddNumber(<span class="built_in">Math</span>.floor(<span class="built_in">Math</span>.random() * (<span class="number">1000</span>)));</span></span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">        <span class="function"><span class="keyword">function</span> <span class="title">AddAllNumber</span><span class="params">()</span> </span>&#123;</span></span><br><span class="line"><span class="actionscript">            <span class="keyword">while</span> (<span class="literal">true</span>) &#123;</span></span><br><span class="line">                AddOneNumber();</span><br><span class="line"><span class="javascript">                <span class="keyword">var</span> numbertext = <span class="built_in">document</span>.getElementById(<span class="string">"numbertext"</span>).value;</span></span><br><span class="line"><span class="javascript">                <span class="keyword">if</span> (!<span class="regexp">/[1-9][0-9]&#123;0,2&#125;/</span>.test(numbertext)) &#123;</span></span><br><span class="line"><span class="actionscript">                    <span class="keyword">break</span>;</span></span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">        <span class="function"><span class="keyword">function</span> <span class="title">AddNumber</span><span class="params">(number)</span> </span>&#123;</span></span><br><span class="line">            tree.Insert(number);</span><br><span class="line">            RenewView(tree);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">        <span class="function"><span class="keyword">function</span> <span class="title">DeleteNumber</span><span class="params">()</span> </span>&#123;</span></span><br><span class="line"><span class="javascript">            <span class="keyword">var</span> deleteNumberText = <span class="built_in">document</span>.getElementById(<span class="string">"deleteNumberText"</span>).value;</span></span><br><span class="line"><span class="javascript">            <span class="keyword">if</span> (!deleteNumberText.match(<span class="regexp">/^[1-9][0-9]&#123;0,2&#125;$/</span>)) &#123;</span></span><br><span class="line"><span class="actionscript">                alert(<span class="string">"请正确输入1-999的整数"</span>);</span></span><br><span class="line"><span class="actionscript">                <span class="keyword">return</span> <span class="literal">false</span>;</span></span><br><span class="line">            &#125;</span><br><span class="line"><span class="javascript">            <span class="keyword">var</span> number = <span class="built_in">parseInt</span>(deleteNumberText);</span></span><br><span class="line"><span class="actionscript">            <span class="keyword">var</span> isExist = tree.Search(number);</span></span><br><span class="line">            if (!isExist)</span><br><span class="line">            &#123;</span><br><span class="line"><span class="actionscript">                alert(<span class="string">"不存在此节点"</span>);</span></span><br><span class="line"><span class="actionscript">                <span class="keyword">return</span> <span class="literal">false</span>;</span></span><br><span class="line">            &#125;</span><br><span class="line">            tree.Remove(number);</span><br><span class="line"><span class="javascript">            <span class="built_in">document</span>.getElementById(<span class="string">"deleteNumberText"</span>).value = <span class="string">''</span>;</span></span><br><span class="line">            RenewView(tree);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">        <span class="function"><span class="keyword">function</span> <span class="title">RenewView</span><span class="params">(_tree)</span> </span>&#123;</span></span><br><span class="line"><span class="javascript">            <span class="keyword">var</span> currentView = <span class="built_in">document</span>.getElementById(<span class="string">"currentView"</span>);</span></span><br><span class="line"><span class="actionscript">            currentView.innerHTML = <span class="string">''</span>;</span></span><br><span class="line">            CreateTreeView(_tree.RootNode, currentView);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="actionscript">        <span class="function"><span class="keyword">function</span> <span class="title">CreateTreeView</span><span class="params">(rootNode, hostDocument)</span> </span>&#123;</span></span><br><span class="line"><span class="actionscript">            <span class="keyword">var</span> size = SetCanvasWidthHeight(rootNode);</span></span><br><span class="line"></span><br><span class="line"><span class="javascript">            <span class="keyword">var</span> canvas = <span class="built_in">document</span>.createElement(<span class="string">"canvas"</span>);</span></span><br><span class="line"><span class="actionscript">            canvas.style.backgroundColor = <span class="string">"antiquewhite"</span>;</span></span><br><span class="line"><span class="actionscript">            canvas.style.display = <span class="string">"block"</span>;</span></span><br><span class="line">            canvas.height = size.height;</span><br><span class="line">            canvas.width = size.width;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="keyword">var</span> context = canvas.getContext(<span class="string">"2d"</span>);</span></span><br><span class="line"></span><br><span class="line">            hostDocument.appendChild(canvas);</span><br><span class="line">            SetPoint(rootNode);</span><br><span class="line">            PreOrder(rootNode, SetPreOrder, context, canvas.width);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="actionscript">        <span class="function"><span class="keyword">function</span> <span class="title">PreOrder</span><span class="params">(node, action, context, canvasWidth)</span> </span>&#123;</span></span><br><span class="line">            action(node, context, canvasWidth);</span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="keyword">if</span> (node.LeftNode != <span class="literal">null</span>) &#123;</span></span><br><span class="line">                PreOrder(node.LeftNode, action, context, canvasWidth);</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="keyword">if</span> (node.RightNode != <span class="literal">null</span>) &#123;</span></span><br><span class="line">                PreOrder(node.RightNode, action, context, canvasWidth);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="actionscript">        <span class="function"><span class="keyword">function</span> <span class="title">SetCanvasWidthHeight</span><span class="params">(rootNode)</span> </span>&#123;</span></span><br><span class="line"><span class="actionscript">            <span class="keyword">var</span> level = Level(rootNode);</span></span><br><span class="line"><span class="actionscript">            <span class="keyword">return</span> &#123;</span></span><br><span class="line">                height: height * level + tops + foot,</span><br><span class="line"><span class="javascript">                width: <span class="built_in">Math</span>.pow(<span class="number">2</span>, level + <span class="number">1</span>) * width + spacing * <span class="number">2</span></span></span><br><span class="line">            &#125;;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">        <span class="function"><span class="keyword">function</span> <span class="title">SetPreOrder</span><span class="params">(node, context, canvasWidth)</span> </span>&#123;</span></span><br><span class="line"><span class="actionscript">            <span class="keyword">var</span> container = drawArc(</span></span><br><span class="line">                context,</span><br><span class="line">                node.Data,</span><br><span class="line">                canvasWidth / 2 + width * node.nodePoint,</span><br><span class="line"><span class="javascript">                (node.nodeLevel * height + <span class="built_in">parseInt</span>(tops)),</span></span><br><span class="line">                node.Color);</span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="keyword">if</span> (node.Parent != <span class="literal">null</span>) &#123;</span></span><br><span class="line"><span class="actionscript">                <span class="keyword">var</span> line = linkNode(</span></span><br><span class="line">                    context,</span><br><span class="line">                    (canvasWidth / 2 + width * node.Parent.nodePoint),</span><br><span class="line"><span class="javascript">                    (node.Parent.nodeLevel * height + <span class="built_in">parseInt</span>(tops)),</span></span><br><span class="line">                    (node.Data, canvasWidth / 2 + width * node.nodePoint),</span><br><span class="line"><span class="javascript">                    (node.nodeLevel * height + <span class="built_in">parseInt</span>(tops)));</span></span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">        <span class="comment">//生产节点</span></span></span><br><span class="line"><span class="actionscript">        <span class="function"><span class="keyword">function</span> <span class="title">drawArc</span><span class="params">(context, number, x, y, color)</span> </span>&#123;</span></span><br><span class="line"><span class="actionscript">            <span class="comment">//圆</span></span></span><br><span class="line">            context.beginPath();</span><br><span class="line">            context.fillStyle = color;</span><br><span class="line"><span class="javascript">            context.arc(x, y, <span class="number">15</span>, (<span class="built_in">Math</span>.PI / <span class="number">180</span>) * <span class="number">0</span>, (<span class="built_in">Math</span>.PI / <span class="number">180</span>) * <span class="number">360</span>, <span class="literal">false</span>);</span></span><br><span class="line">            context.fill();</span><br><span class="line">            context.closePath();</span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="comment">//数字</span></span></span><br><span class="line"><span class="actionscript">            <span class="keyword">var</span> textX = x;</span></span><br><span class="line"><span class="actionscript">            <span class="keyword">var</span> textY = y + <span class="number">5</span>;</span></span><br><span class="line">            if (number &lt; 10) &#123;</span><br><span class="line">                textX -= 5;</span><br><span class="line"><span class="actionscript">            &#125; <span class="keyword">else</span> <span class="keyword">if</span> (number &gt; <span class="number">9</span> &amp;&amp; number &lt; <span class="number">100</span>) &#123;</span></span><br><span class="line">                textX -= 8;</span><br><span class="line"><span class="actionscript">            &#125; <span class="keyword">else</span> &#123;</span></span><br><span class="line">                textX -= 12;</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">            context.fillStyle = <span class="string">"white"</span>;</span></span><br><span class="line"><span class="actionscript">            context.font = <span class="string">"bold 15px Arial"</span>;</span></span><br><span class="line"><span class="actionscript">            context.fillText(number + <span class="string">""</span>, textX, textY);</span></span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">        <span class="comment">//链接节点</span></span></span><br><span class="line"><span class="actionscript">        <span class="function"><span class="keyword">function</span> <span class="title">linkNode</span><span class="params">(context, fatherNodeX, fatherNodeY, childrenNodeX, childrenNodeY)</span> </span>&#123;</span></span><br><span class="line">            drawLine(context, fatherNodeX, fatherNodeY + 15, childrenNodeX, childrenNodeY - 15);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">        <span class="comment">//生产线</span></span></span><br><span class="line"><span class="actionscript">        <span class="function"><span class="keyword">function</span> <span class="title">drawLine</span><span class="params">(context, x, y, toX, toY)</span> </span>&#123;</span></span><br><span class="line">            context.moveTo(x, y);</span><br><span class="line">            context.lineTo(x, y);</span><br><span class="line">            context.lineTo(toX, toY);</span><br><span class="line">            context.stroke();</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="actionscript">        <span class="keyword">var</span> maxLevel;</span></span><br><span class="line"><span class="actionscript">        <span class="keyword">var</span> level;</span></span><br><span class="line"><span class="actionscript">        <span class="function"><span class="keyword">function</span> <span class="title">Level</span><span class="params">(rootNode)</span> </span>&#123;</span></span><br><span class="line">            maxLevel = 0;</span><br><span class="line">            level = 0;</span><br><span class="line"><span class="actionscript">            <span class="keyword">return</span> levels(rootNode);</span></span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">        <span class="function"><span class="keyword">function</span> <span class="title">levels</span><span class="params">(node)</span> </span>&#123;</span></span><br><span class="line"><span class="actionscript">            <span class="keyword">if</span> (node.LeftNode != <span class="literal">null</span>) &#123;</span></span><br><span class="line">                level++;</span><br><span class="line">                levels(node.LeftNode);</span><br><span class="line">            &#125;</span><br><span class="line"><span class="javascript">            maxLevel = <span class="built_in">Math</span>.max(maxLevel, level);</span></span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="keyword">if</span> (node.RightNode != <span class="literal">null</span>) &#123;</span></span><br><span class="line">                level++;</span><br><span class="line">                levels(node.RightNode);</span><br><span class="line">            &#125;</span><br><span class="line">            level--;</span><br><span class="line"><span class="actionscript">            <span class="keyword">return</span> maxLevel;</span></span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">        <span class="function"><span class="keyword">function</span> <span class="title">SetPoint</span><span class="params">(rootNode)</span> </span>&#123;</span></span><br><span class="line"><span class="actionscript">            <span class="keyword">var</span> thisMaxLevel = Level(rootNode);</span></span><br><span class="line"><span class="javascript">            <span class="keyword">var</span> childQuanty = <span class="built_in">Math</span>.pow(<span class="number">2</span>, thisMaxLevel);</span></span><br><span class="line"></span><br><span class="line">            rootNode.nodeLevel = 0;</span><br><span class="line">            rootNode.nodePoint = 0;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="keyword">if</span> (rootNode.LeftNode != <span class="literal">null</span>) &#123;</span></span><br><span class="line">                setPointsLeft(rootNode.LeftNode, -1 * childQuanty / 2, 0, thisMaxLevel - 1);</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="keyword">if</span> (rootNode.RightNode != <span class="literal">null</span>) &#123;</span></span><br><span class="line">                setPointsRight(rootNode.RightNode, childQuanty / 2, 0, thisMaxLevel - 1);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">        <span class="function"><span class="keyword">function</span> <span class="title">setPointsLeft</span><span class="params">(node, point, levels, thisMaxLevel)</span> </span>&#123;</span></span><br><span class="line">            ++levels;</span><br><span class="line">            node.nodeLevel = levels;</span><br><span class="line">            node.nodePoint = point;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="keyword">if</span> (node.LeftNode != <span class="literal">null</span>) &#123;</span></span><br><span class="line"><span class="javascript">                setPointsLeft(node.LeftNode, point - <span class="built_in">Math</span>.pow(<span class="number">2</span>, thisMaxLevel - levels), levels, thisMaxLevel);</span></span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="keyword">if</span> (node.RightNode != <span class="literal">null</span>) &#123;</span></span><br><span class="line"><span class="javascript">                setPointsLeft(node.RightNode, point + <span class="built_in">Math</span>.pow(<span class="number">2</span>, thisMaxLevel - levels), levels, thisMaxLevel);</span></span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">        <span class="function"><span class="keyword">function</span> <span class="title">setPointsRight</span><span class="params">(node, point, levels, thisMaxLevel)</span> </span>&#123;</span></span><br><span class="line">            ++levels;</span><br><span class="line">            node.nodeLevel = levels;</span><br><span class="line">            node.nodePoint = point;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="keyword">if</span> (node.LeftNode != <span class="literal">null</span>) &#123;</span></span><br><span class="line"><span class="javascript">                setPointsRight(node.LeftNode, point - <span class="built_in">Math</span>.pow(<span class="number">2</span>, thisMaxLevel - levels), levels, thisMaxLevel);</span></span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="keyword">if</span> (node.RightNode != <span class="literal">null</span>) &#123;</span></span><br><span class="line"><span class="javascript">                setPointsRight(node.RightNode, point + <span class="built_in">Math</span>.pow(<span class="number">2</span>, thisMaxLevel - levels), levels, thisMaxLevel);</span></span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="actionscript">        <span class="keyword">var</span> stepRemark = &#123;</span></span><br><span class="line"><span class="actionscript">            <span class="string">"insertCaseA1"</span>: &#123;</span></span><br><span class="line"><span class="actionscript">                <span class="string">"title"</span>: <span class="string">"插入节点情况A1"</span>,</span></span><br><span class="line"><span class="actionscript">                <span class="string">"remark"</span>: [</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"当前节点的父节点是红色，且当前节点的祖父节点的另一个子节点（叔叔节点）也是红色"</span></span></span><br><span class="line">                ]</span><br><span class="line">            &#125;,</span><br><span class="line"><span class="actionscript">            <span class="string">"insertSolutionA1"</span>: &#123;</span></span><br><span class="line"><span class="actionscript">                <span class="string">"title"</span>: <span class="string">"插入节点情况A1的解决方案"</span>,</span></span><br><span class="line"><span class="actionscript">                <span class="string">"remark"</span>: [</span></span><br><span class="line"><span class="actionscript">                        <span class="string">"(01) 将“父节点”设为黑色"</span>,</span></span><br><span class="line"><span class="actionscript">                        <span class="string">"(02) 将“叔叔节点”设为黑色"</span>,</span></span><br><span class="line"><span class="actionscript">                        <span class="string">"(03) 将“祖父节点”设为“红色"</span>,</span></span><br><span class="line"><span class="actionscript">                        <span class="string">"(04) 将“祖父节点”设为“当前节点”(红色节点)；即，之后继续对“当前节点”进行操作"</span></span></span><br><span class="line">                ]</span><br><span class="line">            &#125;,</span><br><span class="line"><span class="actionscript">            <span class="string">"insertCaseB1"</span>: &#123;</span></span><br><span class="line"><span class="actionscript">                <span class="string">"title"</span>: <span class="string">"插入节点情况2"</span>,</span></span><br><span class="line"><span class="actionscript">                <span class="string">"remark"</span>: [</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的右孩子"</span></span></span><br><span class="line">                ]</span><br><span class="line">            &#125;,</span><br><span class="line"><span class="actionscript">            <span class="string">"insertSolutionB1"</span>: &#123;</span></span><br><span class="line"><span class="actionscript">                <span class="string">"title"</span>: <span class="string">"插入节点情况2的解决方案"</span>,</span></span><br><span class="line"><span class="actionscript">                <span class="string">"remark"</span>: [</span></span><br><span class="line"><span class="actionscript">                        <span class="string">"(01) 将“父节点”作为“新的当前节点”"</span>,</span></span><br><span class="line"><span class="actionscript">                        <span class="string">"(02) 以“新的当前节点”为支点进行左旋"</span>,</span></span><br><span class="line">                ]</span><br><span class="line">            &#125;,</span><br><span class="line"><span class="actionscript">            <span class="string">"insertCase3"</span>: &#123;</span></span><br><span class="line"><span class="actionscript">                <span class="string">"title"</span>: <span class="string">"插入节点情况3"</span>,</span></span><br><span class="line"><span class="actionscript">                <span class="string">"remark"</span>: [</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的左孩子"</span></span></span><br><span class="line">                ]</span><br><span class="line">            &#125;,</span><br><span class="line"><span class="actionscript">            <span class="string">"insertSolution3"</span>: &#123;</span></span><br><span class="line"><span class="actionscript">                <span class="string">"title"</span>: <span class="string">"插入节点情况3的解决方案"</span>,</span></span><br><span class="line"><span class="actionscript">                <span class="string">"remark"</span>: [</span></span><br><span class="line"><span class="actionscript">                        <span class="string">"(01) 将“父节点”设为“黑色”"</span>,</span></span><br><span class="line"><span class="actionscript">                        <span class="string">"(02) 将“祖父节点”设为“红色”"</span>,</span></span><br><span class="line"><span class="actionscript">                        <span class="string">"(03) 以“祖父节点”为支点进行右旋"</span></span></span><br><span class="line">                ]</span><br><span class="line">            &#125;,</span><br><span class="line"><span class="actionscript">            <span class="string">"insertCase4"</span>: &#123;</span></span><br><span class="line"><span class="actionscript">                <span class="string">"title"</span>: <span class="string">"插入节点情况4"</span>,</span></span><br><span class="line"><span class="actionscript">                <span class="string">"remark"</span>: [</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的左孩子"</span></span></span><br><span class="line">                ]</span><br><span class="line">            &#125;,</span><br><span class="line"><span class="actionscript">            <span class="string">"insertSolution4"</span>: &#123;</span></span><br><span class="line"><span class="actionscript">                <span class="string">"title"</span>: <span class="string">"插入节点情况4的解决方案"</span>,</span></span><br><span class="line"><span class="actionscript">                <span class="string">"remark"</span>: [</span></span><br><span class="line"><span class="actionscript">                        <span class="string">"(01) 将“父节点”作为“新的当前节点”"</span>,</span></span><br><span class="line"><span class="actionscript">                        <span class="string">"(02) 以“新的当前节点”为支点进行右旋"</span>,</span></span><br><span class="line">                ]</span><br><span class="line">            &#125;,</span><br><span class="line"><span class="actionscript">            <span class="string">"insertCase5"</span>: &#123;</span></span><br><span class="line"><span class="actionscript">                <span class="string">"title"</span>: <span class="string">"插入节点情况5"</span>,</span></span><br><span class="line"><span class="actionscript">                <span class="string">"remark"</span>: [</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的右孩子"</span></span></span><br><span class="line">                ]</span><br><span class="line">            &#125;,</span><br><span class="line"><span class="actionscript">            <span class="string">"insertSolution5"</span>: &#123;</span></span><br><span class="line"><span class="actionscript">                <span class="string">"title"</span>: <span class="string">"插入节点情况5的解决方案"</span>,</span></span><br><span class="line"><span class="actionscript">                <span class="string">"remark"</span>: [</span></span><br><span class="line"><span class="actionscript">                        <span class="string">"(01) 将“父节点”设为“黑色”"</span>,</span></span><br><span class="line"><span class="actionscript">                        <span class="string">"(02) 将“祖父节点”设为“红色”"</span>,</span></span><br><span class="line"><span class="actionscript">                        <span class="string">"(03) 以“祖父节点”为支点进行左旋"</span></span></span><br><span class="line">                ]</span><br><span class="line">            &#125;,</span><br><span class="line"><span class="actionscript">            <span class="string">"deleteCase1"</span>: &#123;</span></span><br><span class="line"><span class="actionscript">                <span class="string">"title"</span>: <span class="string">"删除节点情况1"</span>,</span></span><br><span class="line"><span class="actionscript">                <span class="string">"remark"</span>: [</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"被删节点是“黑+黑”节点，被删除的节点是左节点，被删节点的兄弟节点是红色。(此时被删节点的父节点和x的兄弟节点的子节点都是黑节点)。"</span></span></span><br><span class="line">                ]</span><br><span class="line">            &#125;,</span><br><span class="line"><span class="actionscript">            <span class="string">"deleteSolution1"</span>: &#123;</span></span><br><span class="line"><span class="actionscript">                <span class="string">"title"</span>: <span class="string">"删除节点情况1解决方案"</span>,</span></span><br><span class="line"><span class="actionscript">                <span class="string">"remark"</span>: [</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"(01) 将x的兄弟节点设为“黑色”。"</span>,</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"(02) 将x的父节点设为“红色”。"</span>,</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"(03) 对x的父节点进行左旋。"</span>,</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"(04) 左旋后，重新设置x的兄弟节点。"</span></span></span><br><span class="line">                ]</span><br><span class="line">            &#125;,</span><br><span class="line"><span class="actionscript">            <span class="string">"deleteCase2"</span>: &#123;</span></span><br><span class="line"><span class="actionscript">                <span class="string">"title"</span>: <span class="string">"删除节点情况2"</span>,</span></span><br><span class="line"><span class="actionscript">                <span class="string">"remark"</span>: [</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"被删节点是“黑+黑”节点，被删除的节点是右节点，被删节点的兄弟节点是红色。(此时被删节点的父节点和x的兄弟节点的子节点都是黑节点)。"</span></span></span><br><span class="line">                ]</span><br><span class="line">            &#125;,</span><br><span class="line"><span class="actionscript">            <span class="string">"deleteSolution2"</span>: &#123;</span></span><br><span class="line"><span class="actionscript">                <span class="string">"title"</span>: <span class="string">"删除节点情况2解决方案"</span>,</span></span><br><span class="line"><span class="actionscript">                <span class="string">"remark"</span>: [</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"(01) 将被删节点的兄弟节点设为“黑色”。"</span>,</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"(02) 将被删节点的父节点设为“红色”。"</span>,</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"(03) 对被删节点的父节点进行右旋。"</span>,</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"(04) 右旋后，重新设置x的兄弟节点。"</span></span></span><br><span class="line">                ]</span><br><span class="line">            &#125;,</span><br><span class="line"><span class="actionscript">            <span class="string">"deleteCase3"</span>: &#123;</span></span><br><span class="line"><span class="actionscript">                <span class="string">"title"</span>: <span class="string">"删除节点情况3"</span>,</span></span><br><span class="line"><span class="actionscript">                <span class="string">"remark"</span>: [</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"被删节点是“黑+黑”节点，被删节点的兄弟节点是黑色，被删节点的兄弟节点的两个孩子都是黑色。"</span></span></span><br><span class="line">                ]</span><br><span class="line">            &#125;,</span><br><span class="line"><span class="actionscript">            <span class="string">"deleteSolution3"</span>: &#123;</span></span><br><span class="line"><span class="actionscript">                <span class="string">"title"</span>: <span class="string">"删除节点情况3解决方案"</span>,</span></span><br><span class="line"><span class="actionscript">                <span class="string">"remark"</span>: [</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"(01) 将被删节点的兄弟节点设为“红色”。"</span>,</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"(02) 设置“被删节点的父节点”为“新的被删节点节点”。"</span></span></span><br><span class="line">                ]</span><br><span class="line">            &#125;,</span><br><span class="line"><span class="actionscript">            <span class="string">"deleteCase4"</span>: &#123;</span></span><br><span class="line"><span class="actionscript">                <span class="string">"title"</span>: <span class="string">"删除节点情况4"</span>,</span></span><br><span class="line"><span class="actionscript">                <span class="string">"remark"</span>: [</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"将被删节点是“黑+黑”节点，被删节点的兄弟节点是黑色；将被删节点的兄弟节点的左孩子是红色，右孩子是黑色的。"</span></span></span><br><span class="line">                ]</span><br><span class="line">            &#125;,</span><br><span class="line"><span class="actionscript">            <span class="string">"deleteSolution4"</span>: &#123;</span></span><br><span class="line"><span class="actionscript">                <span class="string">"title"</span>: <span class="string">"删除节点情况4解决方案"</span>,</span></span><br><span class="line"><span class="actionscript">                <span class="string">"remark"</span>: [</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"(01) 将被删节点兄弟节点的左孩子设为“黑色”。"</span>,</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"(02) 将被删节点兄弟节点设为“红色”。"</span>,</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"(03) 对被删节点的兄弟节点进行右旋。"</span>,</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"(04) 右旋后，重新设置被删节点的兄弟节点。"</span>,</span></span><br><span class="line">                ]</span><br><span class="line">            &#125;,</span><br><span class="line"><span class="actionscript">            <span class="string">"deleteCase5"</span>: &#123;</span></span><br><span class="line"><span class="actionscript">                <span class="string">"title"</span>: <span class="string">"删除节点情况5"</span>,</span></span><br><span class="line"><span class="actionscript">                <span class="string">"remark"</span>: [</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"被删节点是“黑+黑”节点，被删节点的兄弟节点是黑色；被删节点的兄弟节点的左孩子是黑色，右孩子是红色的。"</span></span></span><br><span class="line">                ]</span><br><span class="line">            &#125;,</span><br><span class="line"><span class="actionscript">            <span class="string">"deleteSolution5"</span>: &#123;</span></span><br><span class="line"><span class="actionscript">                <span class="string">"title"</span>: <span class="string">"删除节点情况5解决方案"</span>,</span></span><br><span class="line"><span class="actionscript">                <span class="string">"remark"</span>: [</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"(01) 将被删节点兄弟节点的右孩子设为“黑色”。"</span>,</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"(02) 将被删节点兄弟节点设为“红色”。"</span>,</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"(03) 对被删节点的兄弟节点进行左旋。"</span>,</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"(04) 左旋后，重新设置被删节点的兄弟节点。"</span>,</span></span><br><span class="line">                ]</span><br><span class="line">            &#125;,</span><br><span class="line"><span class="actionscript">            <span class="string">"deleteCase6"</span>: &#123;</span></span><br><span class="line"><span class="actionscript">                <span class="string">"title"</span>: <span class="string">"删除节点情况6"</span>,</span></span><br><span class="line"><span class="actionscript">                <span class="string">"remark"</span>: [</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"被删节点是“黑+黑”节点，被删节点的兄弟节点是黑色；被删节点的兄弟节点的右孩子是红色的，被删节点的兄弟节点的左孩子任意颜色。"</span></span></span><br><span class="line">                ]</span><br><span class="line">            &#125;,</span><br><span class="line"><span class="actionscript">            <span class="string">"deleteSolution6"</span>: &#123;</span></span><br><span class="line"><span class="actionscript">                <span class="string">"title"</span>: <span class="string">"删除节点情况6解决方案"</span>,</span></span><br><span class="line"><span class="actionscript">                <span class="string">"remark"</span>: [</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"(01) 将被删节点父节点颜色 赋值给 被删节点的兄弟节点。"</span>,</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"(02) 将被删节点父节点设为“黑色”。"</span>,</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"(03) 将被删节点兄弟节点的右子节点设为“黑色”。"</span>,</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"(04) 对被删节点的父节点进行左旋。"</span>,</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"(05) 设置“被删节点”为“根节点”。"</span></span></span><br><span class="line">                ]</span><br><span class="line">            &#125;,</span><br><span class="line"><span class="actionscript">            <span class="string">"deleteCase7"</span>: &#123;</span></span><br><span class="line"><span class="actionscript">                <span class="string">"title"</span>: <span class="string">"删除节点情况7"</span>,</span></span><br><span class="line"><span class="actionscript">                <span class="string">"remark"</span>: [</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"被删节点是“黑+黑”节点，被删节点的兄弟节点是黑色；被删节点的兄弟节点的左孩子是红色的，被删节点的兄弟节点的右孩子任意颜色。"</span></span></span><br><span class="line">                ]</span><br><span class="line">            &#125;,</span><br><span class="line"><span class="actionscript">            <span class="string">"deleteSolution7"</span>: &#123;</span></span><br><span class="line"><span class="actionscript">                <span class="string">"title"</span>: <span class="string">"删除节点情况7解决方案"</span>,</span></span><br><span class="line"><span class="actionscript">                <span class="string">"remark"</span>: [</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"(01) 将被删节点父节点颜色 赋值给 被删节点的兄弟节点。"</span>,</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"(02) 将被删节点父节点设为“黑色”。"</span>,</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"(03) 将被删节点兄弟节点的左子节设为“黑色”。"</span>,</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"(04) 对被删节点的父节点进行右旋。"</span>,</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"(05) 设置“被删节点”为“根节点”。"</span></span></span><br><span class="line">                ]</span><br><span class="line">            &#125;,</span><br><span class="line"><span class="actionscript">            <span class="string">"deleteCase8"</span>: &#123;</span></span><br><span class="line"><span class="actionscript">                <span class="string">"title"</span>: <span class="string">"删除节点情况8"</span>,</span></span><br><span class="line"><span class="actionscript">                <span class="string">"remark"</span>: [</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"被删节点有两个子节点"</span></span></span><br><span class="line">                ]</span><br><span class="line">            &#125;,</span><br><span class="line"><span class="actionscript">            <span class="string">"deleteSolution8"</span>: &#123;</span></span><br><span class="line"><span class="actionscript">                <span class="string">"title"</span>: <span class="string">"删除节点情况8解决方案"</span>,</span></span><br><span class="line"><span class="actionscript">                <span class="string">"remark"</span>: [</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"(01) 将被删节点右节点的子孙节点中找出小的节点，替换被删节点。"</span>,</span></span><br><span class="line">                ]</span><br><span class="line">            &#125;,</span><br><span class="line"><span class="actionscript">            <span class="string">"deleteCase9"</span>: &#123;</span></span><br><span class="line"><span class="actionscript">                <span class="string">"title"</span>: <span class="string">"删除节点情况9"</span>,</span></span><br><span class="line"><span class="actionscript">                <span class="string">"remark"</span>: [</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"被删节点只有一个子节点或无子节点"</span></span></span><br><span class="line">                ]</span><br><span class="line">            &#125;,</span><br><span class="line"><span class="actionscript">            <span class="string">"deleteSolution9"</span>: &#123;</span></span><br><span class="line"><span class="actionscript">                <span class="string">"title"</span>: <span class="string">"删除节点情况9解决方案"</span>,</span></span><br><span class="line"><span class="actionscript">                <span class="string">"remark"</span>: [</span></span><br><span class="line"><span class="actionscript">                    <span class="string">"(01) 将唯一的子节点替换被删节点。"</span>,</span></span><br><span class="line">                ]</span><br><span class="line">            &#125;</span><br><span class="line">                </span><br><span class="line">        &#125;;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">        <span class="function"><span class="keyword">function</span> <span class="title">ClearStepView</span><span class="params">()</span> </span>&#123;</span></span><br><span class="line"><span class="javascript">            <span class="keyword">var</span> stepView = <span class="built_in">document</span>.getElementById(<span class="string">"stepView"</span>);</span></span><br><span class="line"><span class="actionscript">            stepView.innerHTML = <span class="string">''</span>;</span></span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">        <span class="function"><span class="keyword">function</span> <span class="title">CreateStepView</span><span class="params">(_tree, step, currentNumber)</span> </span>&#123;</span></span><br><span class="line"><span class="javascript">            <span class="keyword">var</span> fieldset = <span class="built_in">document</span>.createElement(<span class="string">"fieldset"</span>);</span></span><br><span class="line"><span class="javascript">            <span class="keyword">var</span> legend = <span class="built_in">document</span>.createElement(<span class="string">"legend"</span>);</span></span><br><span class="line"><span class="javascript">            <span class="keyword">var</span> ul = <span class="built_in">document</span>.createElement(<span class="string">"ul"</span>);</span></span><br><span class="line"><span class="javascript">            <span class="keyword">var</span> canvas = <span class="built_in">document</span>.createElement(<span class="string">"canvas"</span>);</span></span><br><span class="line"></span><br><span class="line">            legend.innerHTML = stepRemark[step].title;</span><br><span class="line"></span><br><span class="line">            if (!!currentNumber) &#123;</span><br><span class="line"><span class="javascript">                <span class="keyword">var</span> li = <span class="built_in">document</span>.createElement(<span class="string">"li"</span>);</span></span><br><span class="line"><span class="actionscript">                li.innerHTML = <span class="string">"当前节点："</span> + currentNumber;</span></span><br><span class="line">                ul.appendChild(li);</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="keyword">for</span> (<span class="keyword">var</span> i = <span class="number">0</span>; i &lt; stepRemark[step].remark.length; i++) &#123;</span></span><br><span class="line"><span class="javascript">                <span class="keyword">var</span> li = <span class="built_in">document</span>.createElement(<span class="string">"li"</span>);</span></span><br><span class="line">                li.innerHTML = stepRemark[step].remark[i];</span><br><span class="line">                ul.appendChild(li);</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line">            fieldset.appendChild(legend);</span><br><span class="line">            fieldset.appendChild(ul);</span><br><span class="line">            fieldset.appendChild(canvas);</span><br><span class="line"></span><br><span class="line"><span class="javascript">            <span class="keyword">var</span> stepView = <span class="built_in">document</span>.getElementById(<span class="string">"stepView"</span>);</span></span><br><span class="line">            stepView.appendChild(fieldset);</span><br><span class="line"></span><br><span class="line">            CreateStepTreeView(_tree, canvas);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">        <span class="function"><span class="keyword">function</span> <span class="title">CreateStepTreeView</span><span class="params">(rootNode, canvas)</span> </span>&#123;</span></span><br><span class="line"><span class="actionscript">            <span class="keyword">var</span> size = SetCanvasWidthHeight(rootNode);</span></span><br><span class="line"></span><br><span class="line"><span class="actionscript">            canvas.style.backgroundColor = <span class="string">"antiquewhite"</span>;</span></span><br><span class="line"><span class="actionscript">            canvas.style.display = <span class="string">"block"</span>;</span></span><br><span class="line">            canvas.height = size.height;</span><br><span class="line">            canvas.width = size.width;</span><br><span class="line"></span><br><span class="line"><span class="actionscript">            <span class="keyword">var</span> context = canvas.getContext(<span class="string">"2d"</span>);</span></span><br><span class="line"></span><br><span class="line">            SetPoint(rootNode);</span><br><span class="line">            PreOrder(rootNode, SetPreOrder, context, canvas.width);</span><br><span class="line">        &#125;</span><br><span class="line">    <span class="tag">&lt;/<span class="name">script</span>&gt;</span></span><br><span class="line"><span class="tag">&lt;/<span class="name">body</span>&gt;</span></span><br><span class="line"><span class="tag">&lt;/<span class="name">html</span>&gt;</span></span><br></pre></td></tr></table></figure>

    </article>
    <!-- license  -->
    
        <div class="license-wrapper">
            <p>原文作者：<a href="http://xiaoqixian.github.io.com">XiaoQixian</a>
            <p>原文链接：<a href="http://xiaoqixian.github.io.com/2020/04/26/%E7%BA%A2%E9%BB%91%E6%A0%91/">http://xiaoqixian.github.io.com/2020/04/26/%E7%BA%A2%E9%BB%91%E6%A0%91/</a>
            <p>发表日期：<a href="http://xiaoqixian.github.io.com/2020/04/26/%E7%BA%A2%E9%BB%91%E6%A0%91/">April 26th 2020, 12:00:00 am</a>
            <p>更新日期：<a href="http://xiaoqixian.github.io.com/2020/04/26/%E7%BA%A2%E9%BB%91%E6%A0%91/">April 27th 2020, 2:54:50 pm</a>
            <p>版权声明：本文采用<a rel="license noopener" href="http://creativecommons.org/licenses/by-nc/4.0/" target="_blank">知识共享署名-非商业性使用 4.0 国际许可协议</a>进行许可</p>
        </div>
    
    <!-- paginator  -->
    <ul class="post-paginator">
        <li class="next">
            
                <div class="nextSlogan">Next Post</div>
                <a href= "/2020/05/07/%E8%BF%87%E6%BB%A4%E5%99%A8%E6%A8%A1%E5%BC%8F/" title= "过滤器模式">
                    <div class="nextTitle">过滤器模式</div>
                </a>
            
        </li>
        <li class="previous">
            
                <div class="prevSlogan">Previous Post</div>
                <a href= "/2020/04/16/IntegerProgramming/" title= "Integer Programming">
                    <div class="prevTitle">Integer Programming</div>
                </a>
            
        </li>
    </ul>
    <!-- 评论插件 -->
    <!-- 来必力City版安装代码 -->

<!-- City版安装代码已完成 -->
    
    
    <!-- gitalk评论 -->

    <!-- utteranc评论 -->

    <!-- partial('_partial/comment/changyan') -->
    <!--PC版-->


    
    

    <!-- 评论 -->
</main>
            <!-- profile -->
            
        </div>
        <footer class="footer footer-unloaded">
    <!-- social  -->
    
    <div class="social">
        
    
        
            
                <a href="mailto:lunar_ubuntu@qq.com" class="iconfont-archer email" title=email ></a>
            
        
    
        
            
                <a href="//github.com/xiaoqixian" class="iconfont-archer github" target="_blank" title=github></a>
            
        
    
        
            
                <span class="iconfont-archer wechat" title=wechat>
                  
                  <img class="profile-qr" src="/assets/wukong.png" />
                </span>
            
        
    
        
    
        
    
        
    
        
    
        
    
        
    
        
    
        
    
        
    
        
    
        
    
        
    
        
    
        
    
        
    
        
    
        
    

    </div>
    
    <!-- powered by Hexo  -->
    <div class="copyright">
        <span id="hexo-power">Powered by <a href="https://hexo.io/" target="_blank">Hexo</a></span><span class="iconfont-archer power">&#xe635;</span><span id="theme-info">theme <a href="https://github.com/fi3ework/hexo-theme-archer" target="_blank">Archer</a></span>
    </div>
    <!-- 不蒜子  -->
    
    <div class="busuanzi-container">
    
     
    <span id="busuanzi_container_site_pv">PV: <span id="busuanzi_value_site_pv"></span> :)</span>
    
    </div>
    
</footer>
    </div>
    <!-- toc -->
    
    <div class="toc-wrapper" style=
    







top:50vh;

    >
        <div class="toc-catalog">
            <span class="iconfont-archer catalog-icon">&#xe613;</span><span>CATALOG</span>
        </div>
        <ol class="toc"><li class="toc-item toc-level-3"><a class="toc-link" href="#红黑树-R-B-Tree"><span class="toc-number">1.</span> <span class="toc-text">红黑树(R-B Tree)</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#红黑树的特性"><span class="toc-number">1.1.</span> <span class="toc-text">红黑树的特性</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#红黑树的应用"><span class="toc-number">1.2.</span> <span class="toc-text">红黑树的应用</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#左旋与右旋"><span class="toc-number">1.3.</span> <span class="toc-text">左旋与右旋</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#添加节点"><span class="toc-number">1.4.</span> <span class="toc-text">添加节点</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#删除节点"><span class="toc-number">1.5.</span> <span class="toc-text">删除节点</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#Visualization"><span class="toc-number">1.6.</span> <span class="toc-text">Visualization</span></a></li></ol></li></ol>
    </div>
    
    <div class="back-top iconfont-archer">&#xe639;</div>
    <div class="sidebar sidebar-hide">
    <ul class="sidebar-tabs sidebar-tabs-active-0">
        <li class="sidebar-tab-archives"><span class="iconfont-archer">&#xe67d;</span><span class="tab-name">Archive</span></li>
        <li class="sidebar-tab-tags"><span class="iconfont-archer">&#xe61b;</span><span class="tab-name">Tag</span></li>
        <li class="sidebar-tab-categories"><span class="iconfont-archer">&#xe666;</span><span class="tab-name">Cate</span></li>
    </ul>
    <div class="sidebar-content sidebar-content-show-archive">
          <div class="sidebar-panel-archives">
    <!-- 在ejs中将archive按照时间排序 -->
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    <div class="total-and-search">
        <div class="total-archive">
        Total : 21
        </div>
        <!-- search  -->
        
    </div>
    
    <div class="post-archive">
    
    
    
    
    <div class="archive-year"> 2020 </div>
    <ul class="year-list">
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">06/23</span><a class="archive-post-title" href= "/2020/06/23/%E7%95%99%E6%95%B0/" >留数</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">05/21</span><a class="archive-post-title" href= "/2020/05/21/Linux%E5%A4%9A%E7%BA%BF%E7%A8%8B/" >Linux多线程</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">05/18</span><a class="archive-post-title" href= "/2020/05/18/LinuxSignal/" >Linux Signal</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">05/07</span><a class="archive-post-title" href= "/2020/05/07/%E5%8D%95%E4%BE%8B%E6%A8%A1%E5%BC%8F/" >单例模式</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">05/07</span><a class="archive-post-title" href= "/2020/05/07/%E5%8E%9F%E5%9E%8B%E6%A8%A1%E5%BC%8F/" >原型模式</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">05/07</span><a class="archive-post-title" href= "/2020/05/07/%E5%BB%BA%E9%80%A0%E8%80%85%E6%A8%A1%E5%BC%8F/" >建造者模式</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">05/07</span><a class="archive-post-title" href= "/2020/05/07/%E5%B7%A5%E5%8E%82%E6%A8%A1%E5%BC%8F/" >工厂模式</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">05/07</span><a class="archive-post-title" href= "/2020/05/07/%E6%A1%A5%E6%8E%A5%E6%A8%A1%E5%BC%8F/" >桥接模式</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">05/07</span><a class="archive-post-title" href= "/2020/05/07/%E9%80%82%E9%85%8D%E5%99%A8%E6%A8%A1%E5%BC%8F/" >适配器模式</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">05/07</span><a class="archive-post-title" href= "/2020/05/07/%E8%BF%87%E6%BB%A4%E5%99%A8%E6%A8%A1%E5%BC%8F/" >过滤器模式</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">04/26</span><a class="archive-post-title" href= "/2020/04/26/%E7%BA%A2%E9%BB%91%E6%A0%91/" >红黑树</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">04/16</span><a class="archive-post-title" href= "/2020/04/16/IntegerProgramming/" >Integer Programming</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">04/15</span><a class="archive-post-title" href= "/2020/04/15/%E8%A4%87%E8%AE%8A%E5%87%BD%E6%95%B8%E7%A9%8D%E5%88%86/" >复变函数积分</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">04/12</span><a class="archive-post-title" href= "/2020/04/12/%E5%9F%BA%E6%9C%AC%E6%94%BE%E5%A4%A7%E9%9B%BB%E8%B7%AF/" >基本放大電路</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">04/12</span><a class="archive-post-title" href= "/2020/04/12/ContinuousTimeFourierTransform/" >Continuous Time Fourier Transform</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">04/11</span><a class="archive-post-title" href= "/2020/04/11/Linux%E6%96%87%E4%BB%B6%E6%93%8D%E4%BD%9C%E5%87%BD%E6%95%B8/" >Linux文件操作函數</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">04/11</span><a class="archive-post-title" href= "/2020/04/11/%E6%95%B8%E6%93%9A%E7%9A%84IO%E5%92%8C%E8%A4%87%E7%94%A8/" >数据的IO与复用</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">04/11</span><a class="archive-post-title" href= "/2020/04/11/Hexo%E6%95%B8%E5%AD%B8%E5%85%AC%E5%BC%8F%E6%B8%B2%E6%9F%93%E9%85%8D%E7%BD%AE/" >Hexo數學公式渲染配置</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">04/11</span><a class="archive-post-title" href= "/2020/04/11/LVM/" >LVM</a>
        </li>
    
    
    
    
    
        </ul>
    
    <div class="archive-year"> Invalid date </div>
    <ul class="year-list">
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">Invalid date</span><a class="archive-post-title" href= "/2020/04/10/hello-world/" >Hello World</a>
        </li>
    
    
    
    
    
        </ul>
    
    <div class="archive-year"> 2020 </div>
    <ul class="year-list">
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">04/11</span><a class="archive-post-title" href= "/2020/04/11/Linux%E7%9A%84%E5%B8%B8%E7%94%A8%E7%9B%AE%E9%8C%84/" >Linux的常用目錄</a>
        </li>
    
    </div>
  </div>
        <div class="sidebar-panel-tags">
    <div class="sidebar-tags-name">
    
        <span class="sidebar-tag-name" data-tags="EnvironmentConfiguration"><span class="iconfont-archer">&#xe606;</span>EnvironmentConfiguration</span>
    
        <span class="sidebar-tag-name" data-tags="Hexo"><span class="iconfont-archer">&#xe606;</span>Hexo</span>
    
        <span class="sidebar-tag-name" data-tags="Linux"><span class="iconfont-archer">&#xe606;</span>Linux</span>
    
        <span class="sidebar-tag-name" data-tags="OperatingSystem"><span class="iconfont-archer">&#xe606;</span>OperatingSystem</span>
    
        <span class="sidebar-tag-name" data-tags="OperationResearch"><span class="iconfont-archer">&#xe606;</span>OperationResearch</span>
    
        <span class="sidebar-tag-name" data-tags="FileSystem"><span class="iconfont-archer">&#xe606;</span>FileSystem</span>
    
        <span class="sidebar-tag-name" data-tags="DesignPattern"><span class="iconfont-archer">&#xe606;</span>DesignPattern</span>
    
        <span class="sidebar-tag-name" data-tags="AnalogElectronic"><span class="iconfont-archer">&#xe606;</span>AnalogElectronic</span>
    
        <span class="sidebar-tag-name" data-tags="CircuitAnalysis"><span class="iconfont-archer">&#xe606;</span>CircuitAnalysis</span>
    
        <span class="sidebar-tag-name" data-tags="TCP/IP"><span class="iconfont-archer">&#xe606;</span>TCP/IP</span>
    
        <span class="sidebar-tag-name" data-tags="IO"><span class="iconfont-archer">&#xe606;</span>IO</span>
    
        <span class="sidebar-tag-name" data-tags="ComplexFunction"><span class="iconfont-archer">&#xe606;</span>ComplexFunction</span>
    
        <span class="sidebar-tag-name" data-tags="Linux Programming"><span class="iconfont-archer">&#xe606;</span>Linux Programming</span>
    
        <span class="sidebar-tag-name" data-tags="DataStructure"><span class="iconfont-archer">&#xe606;</span>DataStructure</span>
    
        <span class="sidebar-tag-name" data-tags="BinaryTree"><span class="iconfont-archer">&#xe606;</span>BinaryTree</span>
    
        <span class="sidebar-tag-name" data-tags="Signals&Systems"><span class="iconfont-archer">&#xe606;</span>Signals&Systems</span>
    
        <span class="sidebar-tag-name" data-tags="ComplexFunctions"><span class="iconfont-archer">&#xe606;</span>ComplexFunctions</span>
    
        <span class="sidebar-tag-name" data-tags="Multi-threads"><span class="iconfont-archer">&#xe606;</span>Multi-threads</span>
    
    </div>
    <div class="iconfont-archer sidebar-tags-empty">&#xe678;</div>
    <div class="tag-load-fail" style="display: none; color: #ccc; font-size: 0.6rem;">
    缺失模块。<br/>
    1、请确保node版本大于6.2<br/>
    2、在博客根目录（注意不是archer根目录）执行以下命令：<br/>
    <span style="color: #f75357; font-size: 1rem; line-height: 2rem;">npm i hexo-generator-json-content --save</span><br/>
    3、在根目录_config.yml里添加配置：
    <pre style="color: #787878; font-size: 0.6rem;">
jsonContent:
  meta: false
  pages: false
  posts:
    title: true
    date: true
    path: true
    text: false
    raw: false
    content: false
    slug: false
    updated: false
    comments: false
    link: false
    permalink: false
    excerpt: false
    categories: true
    tags: true</pre>
    </div> 
    <div class="sidebar-tags-list"></div>
</div>
        <div class="sidebar-panel-categories">
    <div class="sidebar-categories-name">
    
        <span class="sidebar-category-name" data-categories="EnvironmentConfiguration"><span class="iconfont-archer">&#xe60a;</span>EnvironmentConfiguration</span>
    
        <span class="sidebar-category-name" data-categories="Linux"><span class="iconfont-archer">&#xe60a;</span>Linux</span>
    
        <span class="sidebar-category-name" data-categories="OperationResearch"><span class="iconfont-archer">&#xe60a;</span>OperationResearch</span>
    
        <span class="sidebar-category-name" data-categories="LinuxFile"><span class="iconfont-archer">&#xe60a;</span>LinuxFile</span>
    
        <span class="sidebar-category-name" data-categories="DesignPattern"><span class="iconfont-archer">&#xe60a;</span>DesignPattern</span>
    
        <span class="sidebar-category-name" data-categories="AnalogElectronic"><span class="iconfont-archer">&#xe60a;</span>AnalogElectronic</span>
    
        <span class="sidebar-category-name" data-categories="TCP-IP"><span class="iconfont-archer">&#xe60a;</span>TCP-IP</span>
    
        <span class="sidebar-category-name" data-categories="ComplexFunction"><span class="iconfont-archer">&#xe60a;</span>ComplexFunction</span>
    
        <span class="sidebar-category-name" data-categories="Linux-Programming"><span class="iconfont-archer">&#xe60a;</span>Linux-Programming</span>
    
        <span class="sidebar-category-name" data-categories="DataStructure"><span class="iconfont-archer">&#xe60a;</span>DataStructure</span>
    
        <span class="sidebar-category-name" data-categories="Signals-Systems"><span class="iconfont-archer">&#xe60a;</span>Signals-Systems</span>
    
        <span class="sidebar-category-name" data-categories="Multi-threads"><span class="iconfont-archer">&#xe60a;</span>Multi-threads</span>
    
    </div>
    <div class="iconfont-archer sidebar-categories-empty">&#xe678;</div>
    <div class="sidebar-categories-list"></div>
</div>
    </div>
</div> 
    <script>
    var siteMeta = {
        root: "/",
        author: "XiaoQixian"
    }
</script>
    <!-- CDN failover -->
    <script src="https://cdn.jsdelivr.net/npm/jquery@3.3.1/dist/jquery.min.js"></script>
    <script type="text/javascript">
        if (typeof window.$ === 'undefined')
        {
            console.warn('jquery load from jsdelivr failed, will load local script')
            document.write('<script src="/lib/jquery.min.js">\x3C/script>')
        }
    </script>
    <script src="/scripts/main.js"></script>
    <!-- algolia -->
    
    <!-- busuanzi  -->
    
    <script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
    
    <!-- CNZZ  -->
    
    </div>
    <!-- async load share.js -->
    
        <script src="/scripts/share.js" async></script>    
     
    </body>
</html>


